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/NetBSD_loop.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:25:53,559 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:25:53,561 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:25:53,570 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:25:53,571 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:25:53,574 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:25:53,575 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:25:53,577 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:25:53,580 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:25:53,581 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:25:53,582 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:25:53,582 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:25:53,594 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:25:53,595 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:25:53,596 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:25:53,596 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:25:53,598 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:25:53,600 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:25:53,601 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:25:53,603 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:25:53,604 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:25:53,607 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:25:53,607 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:25:53,607 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:25:53,608 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:25:53,609 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:25:53,609 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:25:53,610 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:25:53,617 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:25:53,617 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:25:53,618 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:25:53,618 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:25:53,619 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:25:53,619 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:25:53,620 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:25:53,620 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:25:53,635 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:25:53,635 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:25:53,635 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:25:53,636 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:25:53,637 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:25:53,637 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:25:53,637 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:25:53,637 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:25:53,637 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:25:53,638 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:25:53,638 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:25:53,638 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:25:53,638 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:25:53,638 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:25:53,639 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:25:53,639 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:25:53,639 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:25:53,639 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:25:53,639 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:25:53,641 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:25:53,641 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:25:53,694 INFO ]: Repository-Root is: /tmp [2018-06-22 15:25:53,709 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:25:53,716 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:25:53,717 INFO ]: Initializing SmtParser... [2018-06-22 15:25:53,718 INFO ]: SmtParser initialized [2018-06-22 15:25:53,718 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_loop.c.smt2 [2018-06-22 15:25:53,720 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:25:53,811 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_loop.c.smt2 unknown [2018-06-22 15:25:54,099 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_loop.c.smt2 [2018-06-22 15:25:54,103 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:25:54,109 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:25:54,109 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:25:54,109 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:25:54,109 INFO ]: ChcToBoogie initialized [2018-06-22 15:25:54,113 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:25:54" (1/1) ... [2018-06-22 15:25:54,155 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54 Unit [2018-06-22 15:25:54,155 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:25:54,157 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:25:54,157 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:25:54,157 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:25:54,178 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (1/1) ... [2018-06-22 15:25:54,178 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (1/1) ... [2018-06-22 15:25:54,187 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (1/1) ... [2018-06-22 15:25:54,187 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (1/1) ... [2018-06-22 15:25:54,202 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (1/1) ... [2018-06-22 15:25:54,203 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (1/1) ... [2018-06-22 15:25:54,204 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (1/1) ... [2018-06-22 15:25:54,206 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:25:54,206 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:25:54,207 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:25:54,207 INFO ]: RCFGBuilder initialized [2018-06-22 15:25:54,217 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (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:25:54,241 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:25:54,241 INFO ]: Found specification of procedure False [2018-06-22 15:25:54,241 INFO ]: Found implementation of procedure False [2018-06-22 15:25:54,241 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:25:54,241 INFO ]: Found specification of procedure state [2018-06-22 15:25:54,241 INFO ]: Found implementation of procedure state [2018-06-22 15:25:54,241 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:25:54,241 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:25:54,241 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:25:54,430 INFO ]: Using library mode [2018-06-22 15:25:54,431 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:25:54 BoogieIcfgContainer [2018-06-22 15:25:54,431 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:25:54,432 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:25:54,432 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:25:54,435 INFO ]: TraceAbstraction initialized [2018-06-22 15:25:54,435 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:25:54" (1/3) ... [2018-06-22 15:25:54,442 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f779d25 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:25:54, skipping insertion in model container [2018-06-22 15:25:54,442 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:25:54" (2/3) ... [2018-06-22 15:25:54,443 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f779d25 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:25:54, skipping insertion in model container [2018-06-22 15:25:54,443 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:25:54" (3/3) ... [2018-06-22 15:25:54,445 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:25:54,462 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:25:54,475 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:25:54,523 INFO ]: Using default assertion order modulation [2018-06-22 15:25:54,523 INFO ]: Interprodecural is true [2018-06-22 15:25:54,523 INFO ]: Hoare is false [2018-06-22 15:25:54,523 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:25:54,523 INFO ]: Backedges is TWOTRACK [2018-06-22 15:25:54,523 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:25:54,524 INFO ]: Difference is false [2018-06-22 15:25:54,524 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:25:54,524 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:25:54,538 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:25:54,552 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:25:54,553 INFO ]: Found error trace [2018-06-22 15:25:54,553 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:25:54,554 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:25:54,563 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:25:54,564 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:25:54,565 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:25:54,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:25:54,601 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:25:54,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:25:54,636 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:25:54,761 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:25:54,763 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:25:54,763 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:25:54,764 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:25:54,775 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:25:54,775 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:25:54,777 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:25:54,873 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:25:54,874 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:25:54,874 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:25:54,875 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:25:54,876 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:25:54,888 INFO ]: With dead ends: 13 [2018-06-22 15:25:54,888 INFO ]: Without dead ends: 13 [2018-06-22 15:25:54,889 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:25:54,902 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:25:54,923 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:25:54,924 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:25:54,924 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:25:54,925 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:25:54,925 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:25:54,926 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:25:54,926 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:25:54,926 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:25:54,927 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:25:54,927 INFO ]: Found error trace [2018-06-22 15:25:54,927 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:25:54,927 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:25:54,927 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:25:54,927 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:25:54,927 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:25:54,928 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:25:54,928 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:25:54,928 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:25:54,984 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:25:55,255 WARN ]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 15:25:55,385 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:25:55,385 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:25:55,385 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:25:55,393 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:25:55,435 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:25:55,445 INFO ]: Computing forward predicates... [2018-06-22 15:25:55,892 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:25:55,912 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:25:55,912 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:25:55,913 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:25:55,913 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:25:55,913 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:25:55,913 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:25:56,776 WARN ]: Spent 633.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 20 [2018-06-22 15:25:56,962 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 13 [2018-06-22 15:25:56,982 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:25:56,982 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:25:56,983 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:25:56,983 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:25:56,983 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:25:56,984 INFO ]: With dead ends: 15 [2018-06-22 15:25:56,984 INFO ]: Without dead ends: 15 [2018-06-22 15:25:56,985 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:25:56,985 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:25:56,987 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:25:56,987 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:25:56,988 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:25:56,988 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:25:56,988 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:25:56,988 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:25:56,988 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:25:56,988 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:25:56,989 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:25:56,989 INFO ]: Found error trace [2018-06-22 15:25:56,989 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:25:56,989 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:25:56,989 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:25:56,989 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:25:56,989 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:25:56,993 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:25:56,993 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:25:56,993 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:25:57,057 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:25:57,301 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:25:57,301 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:25:57,301 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:25:57,309 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:25:57,358 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:25:57,358 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:25:57,362 INFO ]: Computing forward predicates... [2018-06-22 15:25:57,606 WARN ]: Spent 155.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 19 [2018-06-22 15:25:58,088 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:25:58,121 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:25:58,121 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:25:58,121 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:25:58,121 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:25:58,121 INFO ]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:25:58,122 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:25:58,370 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 36 [2018-06-22 15:25:58,587 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:25:58,587 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:25:58,587 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:25:58,587 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:25:58,587 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:25:58,588 INFO ]: With dead ends: 17 [2018-06-22 15:25:58,588 INFO ]: Without dead ends: 17 [2018-06-22 15:25:58,589 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:25:58,589 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:25:58,592 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:25:58,592 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:25:58,592 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:25:58,592 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:25:58,593 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:25:58,593 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:25:58,593 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:25:58,593 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:25:58,593 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:25:58,593 INFO ]: Found error trace [2018-06-22 15:25:58,593 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:25:58,593 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:25:58,594 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:25:58,594 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:25:58,594 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:25:58,594 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:25:58,595 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:25:58,595 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:25:58,631 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:25:58,853 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:25:58,853 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:25:58,853 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:25:58,865 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:25:58,895 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:25:58,896 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:25:58,899 INFO ]: Computing forward predicates... [2018-06-22 15:25:59,266 WARN ]: Spent 302.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 23 [2018-06-22 15:25:59,443 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 25 [2018-06-22 15:25:59,650 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:25:59,670 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:25:59,670 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-22 15:25:59,671 INFO ]: Interpolant automaton has 14 states [2018-06-22 15:25:59,671 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 15:25:59,671 INFO ]: CoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:25:59,671 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 14 states. [2018-06-22 15:25:59,911 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 43 [2018-06-22 15:26:00,183 WARN ]: Spent 224.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 26 [2018-06-22 15:26:00,331 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 24 [2018-06-22 15:26:00,573 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 29 [2018-06-22 15:26:00,602 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:00,624 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:26:00,625 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:26:00,625 INFO ]: Start accepts. Automaton has 14 states. Word has length 21 [2018-06-22 15:26:00,625 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:00,625 INFO ]: With dead ends: 19 [2018-06-22 15:26:00,625 INFO ]: Without dead ends: 19 [2018-06-22 15:26:00,626 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 16 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=75, Invalid=267, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:26:00,626 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:26:00,628 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:26:00,628 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:26:00,628 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:26:00,628 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:26:00,628 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:00,628 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:26:00,628 INFO ]: Interpolant automaton has 14 states. [2018-06-22 15:26:00,628 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:26:00,630 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:26:00,630 INFO ]: Found error trace [2018-06-22 15:26:00,630 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:00,630 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:00,630 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:26:00,630 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:00,630 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:00,631 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:00,631 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:26:00,631 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:00,675 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:01,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:26:01,099 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:01,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:26:01,105 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:26:01,161 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:26:01,161 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:01,166 INFO ]: Computing forward predicates... [2018-06-22 15:26:01,730 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 23 [2018-06-22 15:26:01,971 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:26:01,990 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:26:01,990 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 17 [2018-06-22 15:26:01,990 INFO ]: Interpolant automaton has 17 states [2018-06-22 15:26:01,990 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 15:26:01,990 INFO ]: CoverageRelationStatistics Valid=43, Invalid=229, Unknown=0, NotChecked=0, Total=272 [2018-06-22 15:26:01,990 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 17 states. [2018-06-22 15:26:02,257 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 41 [2018-06-22 15:26:02,403 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 25 [2018-06-22 15:26:02,661 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 30 [2018-06-22 15:26:02,826 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 28 [2018-06-22 15:26:03,013 WARN ]: Spent 166.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 33 [2018-06-22 15:26:03,042 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:03,042 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:26:03,043 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:26:03,043 INFO ]: Start accepts. Automaton has 17 states. Word has length 25 [2018-06-22 15:26:03,044 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:03,044 INFO ]: With dead ends: 21 [2018-06-22 15:26:03,044 INFO ]: Without dead ends: 21 [2018-06-22 15:26:03,045 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 59 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=104, Invalid=402, Unknown=0, NotChecked=0, Total=506 [2018-06-22 15:26:03,045 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:26:03,048 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:26:03,048 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:26:03,048 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:26:03,049 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:26:03,049 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:03,049 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:26:03,049 INFO ]: Interpolant automaton has 17 states. [2018-06-22 15:26:03,049 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:26:03,049 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:26:03,050 INFO ]: Found error trace [2018-06-22 15:26:03,050 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:03,050 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:03,050 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:26:03,050 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:03,050 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:03,051 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:03,051 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:26:03,051 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:03,100 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:03,518 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:26:03,518 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:03,518 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:26:03,525 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:26:03,584 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:26:03,585 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:03,590 INFO ]: Computing forward predicates... [2018-06-22 15:26:04,329 WARN ]: Spent 515.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 32 [2018-06-22 15:26:06,645 WARN ]: Spent 2.00 s on a formula simplification. DAG size of input: 27 DAG size of output: 25 [2018-06-22 15:26:07,532 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:26:07,551 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:26:07,551 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 15:26:07,551 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:26:07,552 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:26:07,552 INFO ]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:26:07,552 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 20 states. [2018-06-22 15:26:07,974 WARN ]: Spent 388.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 45 [2018-06-22 15:26:08,123 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 29 [2018-06-22 15:26:08,322 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 33 [2018-06-22 15:26:08,540 WARN ]: Spent 197.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 32 [2018-06-22 15:26:08,718 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 31 [2018-06-22 15:26:09,053 WARN ]: Spent 313.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 38 [2018-06-22 15:26:09,083 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:09,083 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:26:09,086 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:26:09,086 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-22 15:26:09,087 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:09,087 INFO ]: With dead ends: 23 [2018-06-22 15:26:09,087 INFO ]: Without dead ends: 23 [2018-06-22 15:26:09,088 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 22 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=141, Invalid=509, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:26:09,088 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:26:09,093 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:26:09,094 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:26:09,094 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:26:09,094 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:26:09,095 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:09,095 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:26:09,095 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:26:09,095 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:26:09,095 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:26:09,095 INFO ]: Found error trace [2018-06-22 15:26:09,096 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:09,096 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:09,098 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:26:09,098 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:09,098 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:09,099 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:09,099 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:26:09,099 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:09,184 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:09,849 WARN ]: Spent 442.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:26:10,689 WARN ]: Spent 768.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 15:26:11,117 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:26:11,117 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:11,117 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:26:11,123 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:26:11,201 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:26:11,201 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:11,206 INFO ]: Computing forward predicates... [2018-06-22 15:26:12,088 WARN ]: Spent 531.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 49 [2018-06-22 15:26:12,350 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 26 [2018-06-22 15:26:13,473 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:26:13,504 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:26:13,504 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 21 [2018-06-22 15:26:13,505 INFO ]: Interpolant automaton has 21 states [2018-06-22 15:26:13,505 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 15:26:13,505 INFO ]: CoverageRelationStatistics Valid=62, Invalid=358, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:26:13,505 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 21 states. [2018-06-22 15:26:13,871 WARN ]: Spent 335.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 44 [2018-06-22 15:26:14,156 WARN ]: Spent 253.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 28 [2018-06-22 15:26:14,488 WARN ]: Spent 307.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 35 [2018-06-22 15:26:14,677 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 25 [2018-06-22 15:26:14,979 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 28 [2018-06-22 15:26:15,267 WARN ]: Spent 264.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 26 [2018-06-22 15:26:15,549 WARN ]: Spent 257.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 29 [2018-06-22 15:26:15,588 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:15,588 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:26:15,589 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:26:15,589 INFO ]: Start accepts. Automaton has 21 states. Word has length 33 [2018-06-22 15:26:15,589 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:15,590 INFO ]: With dead ends: 25 [2018-06-22 15:26:15,590 INFO ]: Without dead ends: 25 [2018-06-22 15:26:15,590 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 25 SyntacticMatches, 4 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 108 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=157, Invalid=599, Unknown=0, NotChecked=0, Total=756 [2018-06-22 15:26:15,590 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:26:15,594 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:26:15,594 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:26:15,594 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:26:15,595 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:26:15,595 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:15,595 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:26:15,595 INFO ]: Interpolant automaton has 21 states. [2018-06-22 15:26:15,595 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:26:15,596 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:26:15,596 INFO ]: Found error trace [2018-06-22 15:26:15,596 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:15,596 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:15,596 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:26:15,596 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:15,596 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:15,597 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:15,597 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:26:15,597 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:15,662 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:16,553 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:26:16,554 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:16,554 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:26:16,561 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:26:16,608 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:16,614 INFO ]: Computing forward predicates... [2018-06-22 15:26:17,361 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:26:17,381 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:26:17,382 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 26 [2018-06-22 15:26:17,382 INFO ]: Interpolant automaton has 26 states [2018-06-22 15:26:17,382 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 15:26:17,382 INFO ]: CoverageRelationStatistics Valid=70, Invalid=580, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:26:17,383 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 26 states. [2018-06-22 15:26:17,775 WARN ]: Spent 354.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 51 [2018-06-22 15:26:17,955 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 30 [2018-06-22 15:26:18,244 WARN ]: Spent 264.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 33 [2018-06-22 15:26:18,488 WARN ]: Spent 218.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 28 [2018-06-22 15:26:18,828 WARN ]: Spent 245.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 30 [2018-06-22 15:26:19,134 WARN ]: Spent 281.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 34 [2018-06-22 15:26:19,409 WARN ]: Spent 248.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 31 [2018-06-22 15:26:19,607 WARN ]: Spent 172.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 30 [2018-06-22 15:26:19,641 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:19,641 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:26:19,641 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:26:19,641 INFO ]: Start accepts. Automaton has 26 states. Word has length 37 [2018-06-22 15:26:19,641 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:19,642 INFO ]: With dead ends: 27 [2018-06-22 15:26:19,642 INFO ]: Without dead ends: 27 [2018-06-22 15:26:19,643 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=215, Invalid=975, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 15:26:19,643 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:26:19,649 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:26:19,649 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:26:19,650 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:26:19,650 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:26:19,650 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:19,650 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:26:19,650 INFO ]: Interpolant automaton has 26 states. [2018-06-22 15:26:19,650 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:26:19,651 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:26:19,651 INFO ]: Found error trace [2018-06-22 15:26:19,651 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:19,651 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:19,651 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 15:26:19,651 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:19,651 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:19,652 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:19,652 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:26:19,652 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:19,762 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:20,765 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:26:20,765 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:20,765 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:26:20,771 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:26:20,826 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:26:20,826 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:20,833 INFO ]: Computing forward predicates... [2018-06-22 15:26:21,007 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 23 [2018-06-22 15:26:21,269 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 32 [2018-06-22 15:26:21,646 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 26 [2018-06-22 15:26:23,308 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:26:23,327 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:26:23,327 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 37 [2018-06-22 15:26:23,328 INFO ]: Interpolant automaton has 37 states [2018-06-22 15:26:23,328 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-22 15:26:23,328 INFO ]: CoverageRelationStatistics Valid=107, Invalid=1225, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 15:26:23,328 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 37 states. [2018-06-22 15:26:24,110 WARN ]: Spent 707.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 103 [2018-06-22 15:26:24,472 WARN ]: Spent 292.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 49 [2018-06-22 15:26:24,822 WARN ]: Spent 223.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 50 [2018-06-22 15:26:25,328 WARN ]: Spent 391.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 55 [2018-06-22 15:26:25,827 WARN ]: Spent 446.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 55 [2018-06-22 15:26:26,309 WARN ]: Spent 392.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 54 [2018-06-22 15:26:26,801 WARN ]: Spent 419.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 54 [2018-06-22 15:26:27,232 WARN ]: Spent 370.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 46 [2018-06-22 15:26:27,766 WARN ]: Spent 475.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 80 [2018-06-22 15:26:27,812 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:27,812 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:26:27,812 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:26:27,812 INFO ]: Start accepts. Automaton has 37 states. Word has length 41 [2018-06-22 15:26:27,812 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:27,813 INFO ]: With dead ends: 29 [2018-06-22 15:26:27,813 INFO ]: Without dead ends: 29 [2018-06-22 15:26:27,813 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=310, Invalid=1852, Unknown=0, NotChecked=0, Total=2162 [2018-06-22 15:26:27,814 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:26:27,817 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:26:27,817 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:26:27,818 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:26:27,818 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:26:27,818 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:27,818 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:26:27,818 INFO ]: Interpolant automaton has 37 states. [2018-06-22 15:26:27,818 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:26:27,819 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:26:27,819 INFO ]: Found error trace [2018-06-22 15:26:27,819 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:27,819 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:27,819 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 15:26:27,819 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:27,819 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:27,820 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:27,820 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:26:27,820 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:27,916 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:28,746 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 28 [2018-06-22 15:26:29,297 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:26:29,297 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:29,297 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:26:29,303 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:26:29,372 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:26:29,372 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:29,380 INFO ]: Computing forward predicates... [2018-06-22 15:26:29,698 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 24 [2018-06-22 15:26:29,931 WARN ]: Spent 194.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 33 [2018-06-22 15:26:30,351 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 26 [2018-06-22 15:26:30,617 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 29 [2018-06-22 15:26:32,326 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:26:32,345 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:26:32,345 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 35 [2018-06-22 15:26:32,346 INFO ]: Interpolant automaton has 35 states [2018-06-22 15:26:32,346 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 15:26:32,346 INFO ]: CoverageRelationStatistics Valid=100, Invalid=1090, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 15:26:32,346 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 35 states. [2018-06-22 15:26:33,099 WARN ]: Spent 673.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 91 [2018-06-22 15:26:33,363 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 32 [2018-06-22 15:26:33,847 WARN ]: Spent 436.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 49 [2018-06-22 15:26:34,237 WARN ]: Spent 351.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 52 [2018-06-22 15:26:34,655 WARN ]: Spent 377.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 52 [2018-06-22 15:26:35,007 WARN ]: Spent 310.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 53 [2018-06-22 15:26:35,431 WARN ]: Spent 384.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 54 [2018-06-22 15:26:36,169 WARN ]: Spent 693.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 67 [2018-06-22 15:26:36,500 WARN ]: Spent 288.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 48 [2018-06-22 15:26:37,139 WARN ]: Spent 599.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 61 [2018-06-22 15:26:37,181 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:37,181 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:26:37,188 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:26:37,188 INFO ]: Start accepts. Automaton has 35 states. Word has length 45 [2018-06-22 15:26:37,188 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:37,189 INFO ]: With dead ends: 31 [2018-06-22 15:26:37,189 INFO ]: Without dead ends: 31 [2018-06-22 15:26:37,190 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 29 SyntacticMatches, 4 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 259 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=313, Invalid=1667, Unknown=0, NotChecked=0, Total=1980 [2018-06-22 15:26:37,190 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:26:37,197 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:26:37,197 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:26:37,198 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:26:37,198 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:26:37,198 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:37,198 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:26:37,199 INFO ]: Interpolant automaton has 35 states. [2018-06-22 15:26:37,199 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:26:37,199 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:26:37,199 INFO ]: Found error trace [2018-06-22 15:26:37,199 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:37,199 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:37,200 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-22 15:26:37,200 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:37,200 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:37,200 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:37,200 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:26:37,200 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:37,292 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:37,969 WARN ]: Spent 484.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 15:26:38,862 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:26:38,862 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:38,862 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:26:38,869 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:26:38,939 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:26:38,939 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:38,946 INFO ]: Computing forward predicates... [2018-06-22 15:26:39,263 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 29 [2018-06-22 15:26:39,426 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 29 [2018-06-22 15:26:39,702 WARN ]: Spent 237.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 37 [2018-06-22 15:26:39,980 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 32 [2018-06-22 15:26:42,732 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:26:42,752 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:26:42,752 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 43 [2018-06-22 15:26:42,753 INFO ]: Interpolant automaton has 43 states [2018-06-22 15:26:42,753 INFO ]: Constructing interpolant automaton starting with 43 interpolants. [2018-06-22 15:26:42,754 INFO ]: CoverageRelationStatistics Valid=118, Invalid=1688, Unknown=0, NotChecked=0, Total=1806 [2018-06-22 15:26:42,754 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 43 states. [2018-06-22 15:26:43,951 WARN ]: Spent 1.11 s on a formula simplification. DAG size of input: 133 DAG size of output: 111 [2018-06-22 15:26:44,543 WARN ]: Spent 431.00 ms on a formula simplification. DAG size of input: 136 DAG size of output: 46 [2018-06-22 15:26:45,237 WARN ]: Spent 630.00 ms on a formula simplification. DAG size of input: 136 DAG size of output: 70 [2018-06-22 15:26:45,871 WARN ]: Spent 567.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 74 [2018-06-22 15:26:46,439 WARN ]: Spent 512.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 71 [2018-06-22 15:26:47,122 WARN ]: Spent 627.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 78 [2018-06-22 15:26:47,577 WARN ]: Spent 401.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 68 [2018-06-22 15:26:48,113 WARN ]: Spent 472.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 75 [2018-06-22 15:26:48,658 WARN ]: Spent 478.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 67 [2018-06-22 15:26:49,280 WARN ]: Spent 485.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 65 [2018-06-22 15:26:50,362 WARN ]: Spent 788.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 88 [2018-06-22 15:26:50,421 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:50,421 INFO ]: Finished difference Result 33 states and 34 transitions. [2018-06-22 15:26:50,421 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 15:26:50,421 INFO ]: Start accepts. Automaton has 43 states. Word has length 49 [2018-06-22 15:26:50,422 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:50,422 INFO ]: With dead ends: 33 [2018-06-22 15:26:50,422 INFO ]: Without dead ends: 33 [2018-06-22 15:26:50,424 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 340 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=399, Invalid=2463, Unknown=0, NotChecked=0, Total=2862 [2018-06-22 15:26:50,424 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 15:26:50,431 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-22 15:26:50,431 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-22 15:26:50,432 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 34 transitions. [2018-06-22 15:26:50,432 INFO ]: Start accepts. Automaton has 33 states and 34 transitions. Word has length 49 [2018-06-22 15:26:50,432 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:50,432 INFO ]: Abstraction has 33 states and 34 transitions. [2018-06-22 15:26:50,432 INFO ]: Interpolant automaton has 43 states. [2018-06-22 15:26:50,432 INFO ]: Start isEmpty. Operand 33 states and 34 transitions. [2018-06-22 15:26:50,433 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 15:26:50,433 INFO ]: Found error trace [2018-06-22 15:26:50,433 INFO ]: trace histogram [12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:50,433 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:50,433 INFO ]: Analyzing trace with hash 1955719355, now seen corresponding path program 11 times [2018-06-22 15:26:50,433 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:50,433 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:50,434 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:50,434 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:26:50,434 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:50,551 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:51,109 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 39 [2018-06-22 15:26:52,103 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:26:52,103 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:52,103 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:26:52,109 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:26:52,215 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-22 15:26:52,215 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:52,222 INFO ]: Computing forward predicates... [2018-06-22 15:26:52,613 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 29 [2018-06-22 15:26:52,780 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 29 [2018-06-22 15:26:53,066 WARN ]: Spent 236.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 37 [2018-06-22 15:26:53,377 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 35 [2018-06-22 15:26:53,663 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 33 Received shutdown request... [2018-06-22 15:26:54,315 INFO ]: Timeout while computing interpolants [2018-06-22 15:26:54,515 WARN ]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:26:54,515 WARN ]: Verification canceled [2018-06-22 15:26:54,519 WARN ]: Timeout [2018-06-22 15:26:54,519 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:26:54 BoogieIcfgContainer [2018-06-22 15:26:54,519 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:26:54,520 INFO ]: Toolchain (without parser) took 60416.02 ms. Allocated memory was 302.0 MB in the beginning and 698.4 MB in the end (delta: 396.4 MB). Free memory was 254.4 MB in the beginning and 607.5 MB in the end (delta: -353.1 MB). Peak memory consumption was 43.3 MB. Max. memory is 3.6 GB. [2018-06-22 15:26:54,520 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 302.0 MB. Free memory is still 266.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:26:54,521 INFO ]: ChcToBoogie took 46.31 ms. Allocated memory is still 302.0 MB. Free memory was 254.4 MB in the beginning and 252.4 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:26:54,521 INFO ]: Boogie Preprocessor took 48.88 ms. Allocated memory is still 302.0 MB. Free memory was 252.4 MB in the beginning and 250.4 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:26:54,521 INFO ]: RCFGBuilder took 224.14 ms. Allocated memory is still 302.0 MB. Free memory was 250.4 MB in the beginning and 240.4 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:26:54,521 INFO ]: TraceAbstraction took 60087.02 ms. Allocated memory was 302.0 MB in the beginning and 698.4 MB in the end (delta: 396.4 MB). Free memory was 240.4 MB in the beginning and 607.5 MB in the end (delta: -367.1 MB). Peak memory consumption was 29.3 MB. Max. memory is 3.6 GB. [2018-06-22 15:26:54,523 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 302.0 MB. Free memory is still 266.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 46.31 ms. Allocated memory is still 302.0 MB. Free memory was 254.4 MB in the beginning and 252.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 48.88 ms. Allocated memory is still 302.0 MB. Free memory was 252.4 MB in the beginning and 250.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 224.14 ms. Allocated memory is still 302.0 MB. Free memory was 250.4 MB in the beginning and 240.4 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 60087.02 ms. Allocated memory was 302.0 MB in the beginning and 698.4 MB in the end (delta: 396.4 MB). Free memory was 240.4 MB in the beginning and 607.5 MB in the end (delta: -367.1 MB). Peak memory consumption was 29.3 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 54 with TraceHistMax 12, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 9 quantified variables from 3 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 60.0s OverallTime, 12 OverallIterations, 12 TraceHistogramMax, 26.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 161 SDtfs, 679 SDslu, 1413 SDs, 0 SdLazy, 1289 SolverSat, 812 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 525 GetRequests, 223 SyntacticMatches, 16 SemanticMatches, 286 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1259 ImplicationChecksByTransitivity, 43.3s 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.1s SsaConstructionTime, 1.1s SatisfiabilityAnalysisTime, 27.5s InterpolantComputationTime, 629 NumberOfCodeBlocks, 629 NumberOfCodeBlocksAsserted, 46 NumberOfCheckSat, 608 ConstructedInterpolants, 0 QuantifiedInterpolants, 506752 SizeOfPredicates, 974 NumberOfNonLiveVariables, 2715 ConjunctsInSsa, 544 ConjunctsInUnsatCore, 21 InterpolantComputations, 1 PerfectInterpolantSequences, 440/1650 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/NetBSD_loop.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-26-54-535.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/NetBSD_loop.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-26-54-535.csv Completed graceful shutdown