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/nested9.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:18:08,409 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:18:08,413 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:18:08,425 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:18:08,427 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:18:08,428 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:18:08,429 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:18:08,431 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:18:08,432 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:18:08,434 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:18:08,435 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:18:08,435 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:18:08,436 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:18:08,440 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:18:08,441 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:18:08,441 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:18:08,444 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:18:08,446 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:18:08,447 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:18:08,448 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:18:08,449 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:18:08,451 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:18:08,451 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:18:08,451 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:18:08,452 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:18:08,453 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:18:08,454 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:18:08,454 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:18:08,455 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:18:08,455 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:18:08,456 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:18:08,457 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:18:08,457 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:18:08,458 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:18:08,458 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:18:08,458 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:18:08,473 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:18:08,473 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:18:08,473 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:18:08,474 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:18:08,475 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:18:08,475 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:18:08,475 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:18:08,475 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:18:08,475 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:18:08,476 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:18:08,476 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:18:08,476 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:18:08,476 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:18:08,476 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:18:08,477 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:18:08,477 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:18:08,477 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:18:08,477 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:18:08,477 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:18:08,479 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:18:08,483 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:18:08,527 INFO ]: Repository-Root is: /tmp [2018-06-22 15:18:08,542 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:18:08,548 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:18:08,549 INFO ]: Initializing SmtParser... [2018-06-22 15:18:08,549 INFO ]: SmtParser initialized [2018-06-22 15:18:08,550 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested9.c.smt2 [2018-06-22 15:18:08,551 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:18:08,641 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested9.c.smt2 unknown [2018-06-22 15:18:08,918 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested9.c.smt2 [2018-06-22 15:18:08,925 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:18:08,931 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:18:08,931 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:18:08,931 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:18:08,931 INFO ]: ChcToBoogie initialized [2018-06-22 15:18:08,935 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:18:08" (1/1) ... [2018-06-22 15:18:08,981 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08 Unit [2018-06-22 15:18:08,981 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:18:08,982 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:18:08,982 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:18:08,982 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:18:09,007 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (1/1) ... [2018-06-22 15:18:09,007 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (1/1) ... [2018-06-22 15:18:09,016 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (1/1) ... [2018-06-22 15:18:09,016 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (1/1) ... [2018-06-22 15:18:09,020 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (1/1) ... [2018-06-22 15:18:09,021 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (1/1) ... [2018-06-22 15:18:09,023 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (1/1) ... [2018-06-22 15:18:09,025 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:18:09,025 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:18:09,025 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:18:09,026 INFO ]: RCFGBuilder initialized [2018-06-22 15:18:09,026 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:18:09,040 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:18:09,040 INFO ]: Found specification of procedure False [2018-06-22 15:18:09,040 INFO ]: Found implementation of procedure False [2018-06-22 15:18:09,040 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:18:09,040 INFO ]: Found specification of procedure state [2018-06-22 15:18:09,040 INFO ]: Found implementation of procedure state [2018-06-22 15:18:09,040 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:18:09,040 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:18:09,040 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 15:18:09,226 INFO ]: Using library mode [2018-06-22 15:18:09,227 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:18:09 BoogieIcfgContainer [2018-06-22 15:18:09,229 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:18:09,231 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:18:09,231 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:18:09,242 INFO ]: TraceAbstraction initialized [2018-06-22 15:18:09,243 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:18:08" (1/3) ... [2018-06-22 15:18:09,243 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@a6087b5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:18:09, skipping insertion in model container [2018-06-22 15:18:09,243 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:18:08" (2/3) ... [2018-06-22 15:18:09,244 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@a6087b5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:18:09, skipping insertion in model container [2018-06-22 15:18:09,244 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:18:09" (3/3) ... [2018-06-22 15:18:09,246 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:18:09,260 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:18:09,282 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:18:09,355 INFO ]: Using default assertion order modulation [2018-06-22 15:18:09,355 INFO ]: Interprodecural is true [2018-06-22 15:18:09,355 INFO ]: Hoare is false [2018-06-22 15:18:09,355 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:18:09,355 INFO ]: Backedges is TWOTRACK [2018-06-22 15:18:09,355 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:18:09,356 INFO ]: Difference is false [2018-06-22 15:18:09,356 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:18:09,356 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:18:09,378 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:18:09,389 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:18:09,389 INFO ]: Found error trace [2018-06-22 15:18:09,390 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:09,390 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:09,394 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:18:09,395 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:09,395 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:09,428 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:09,428 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:18:09,428 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:09,453 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:09,545 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:18:09,547 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:18:09,547 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:18:09,549 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:18:09,562 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:18:09,562 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:18:09,564 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:18:09,635 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:09,635 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:18:09,636 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:18:09,637 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:18:09,637 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:09,646 INFO ]: With dead ends: 13 [2018-06-22 15:18:09,646 INFO ]: Without dead ends: 13 [2018-06-22 15:18:09,648 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:18:09,660 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:18:09,680 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:18:09,681 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:18:09,682 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:18:09,683 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:18:09,683 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:09,683 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:18:09,683 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:18:09,683 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:18:09,684 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:18:09,684 INFO ]: Found error trace [2018-06-22 15:18:09,684 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:09,684 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:09,685 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:18:09,685 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:09,685 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:09,685 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:09,685 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:18:09,686 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:09,745 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:10,011 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:18:10,012 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:10,012 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:18:10,020 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:18:10,071 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:10,081 INFO ]: Computing forward predicates... [2018-06-22 15:18:10,579 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:18:10,598 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:10,599 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:18:10,599 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:18:10,599 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:18:10,599 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:18:10,600 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:18:11,027 WARN ]: Spent 257.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:18:11,122 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:11,122 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:18:11,122 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:18:11,122 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:18:11,123 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:11,123 INFO ]: With dead ends: 15 [2018-06-22 15:18:11,123 INFO ]: Without dead ends: 15 [2018-06-22 15:18:11,124 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:18:11,124 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:18:11,127 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:18:11,127 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:18:11,128 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:18:11,128 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:18:11,128 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:11,128 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:18:11,128 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:18:11,128 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:18:11,129 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:18:11,129 INFO ]: Found error trace [2018-06-22 15:18:11,129 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:11,129 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:11,129 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:18:11,129 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:11,129 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:11,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:11,130 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:18:11,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:11,176 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:11,713 WARN ]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 15:18:11,898 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:18:11,898 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:11,898 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:18:11,907 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:18:11,963 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:18:11,963 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:11,967 INFO ]: Computing forward predicates... [2018-06-22 15:18:12,309 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 16 [2018-06-22 15:18:12,491 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:18:12,514 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:12,514 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:18:12,514 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:18:12,514 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:18:12,514 INFO ]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:18:12,515 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:18:12,738 WARN ]: Spent 173.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 25 [2018-06-22 15:18:12,944 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:12,944 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:18:12,945 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:18:12,945 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:18:12,945 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:12,945 INFO ]: With dead ends: 17 [2018-06-22 15:18:12,945 INFO ]: Without dead ends: 17 [2018-06-22 15:18:12,946 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=50, Invalid=160, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:18:12,946 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:18:12,947 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:18:12,947 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:18:12,948 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:18:12,948 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:18:12,948 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:12,948 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:18:12,948 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:18:12,948 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:18:12,949 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:18:12,949 INFO ]: Found error trace [2018-06-22 15:18:12,949 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:12,949 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:12,949 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:18:12,949 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:12,949 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:12,950 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:12,950 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:12,950 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:12,997 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:13,264 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:18:13,264 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:13,264 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:18:13,279 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:18:13,364 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:18:13,364 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:13,368 INFO ]: Computing forward predicates... [2018-06-22 15:18:14,811 WARN ]: Spent 1.01 s on a formula simplification. DAG size of input: 124 DAG size of output: 28 [2018-06-22 15:18:15,194 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:18:15,220 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:15,220 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-22 15:18:15,221 INFO ]: Interpolant automaton has 14 states [2018-06-22 15:18:15,221 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 15:18:15,221 INFO ]: CoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:18:15,221 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 14 states. [2018-06-22 15:18:15,430 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 35 [2018-06-22 15:18:15,566 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 25 [2018-06-22 15:18:15,734 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 27 [2018-06-22 15:18:15,892 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 30 [2018-06-22 15:18:15,923 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:15,924 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:18:15,925 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:18:15,925 INFO ]: Start accepts. Automaton has 14 states. Word has length 21 [2018-06-22 15:18:15,925 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:15,926 INFO ]: With dead ends: 19 [2018-06-22 15:18:15,926 INFO ]: Without dead ends: 19 [2018-06-22 15:18:15,926 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=76, Invalid=230, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:18:15,926 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:18:15,932 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:18:15,932 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:18:15,933 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:18:15,933 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:18:15,933 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:15,933 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:18:15,933 INFO ]: Interpolant automaton has 14 states. [2018-06-22 15:18:15,933 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:18:15,934 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:18:15,934 INFO ]: Found error trace [2018-06-22 15:18:15,934 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:15,934 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:15,934 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:18:15,934 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:15,934 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:15,935 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:15,935 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:15,935 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:15,984 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:16,346 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:18:16,346 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:16,346 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:18:16,352 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:18:16,401 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:18:16,402 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:16,406 INFO ]: Computing forward predicates... [2018-06-22 15:18:16,667 WARN ]: Spent 161.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 26 [2018-06-22 15:18:19,013 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 2 [2018-06-22 15:18:19,040 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:18:19,071 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:19,071 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 15 [2018-06-22 15:18:19,071 INFO ]: Interpolant automaton has 15 states [2018-06-22 15:18:19,071 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 15:18:19,072 INFO ]: CoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:18:19,072 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 15 states. [2018-06-22 15:18:19,579 WARN ]: Spent 319.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 44 [2018-06-22 15:18:19,726 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 24 [2018-06-22 15:18:19,990 WARN ]: Spent 248.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 32 [2018-06-22 15:18:20,169 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 33 [2018-06-22 15:18:20,372 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 36 [2018-06-22 15:18:20,399 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:20,399 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:18:20,403 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:18:20,403 INFO ]: Start accepts. Automaton has 15 states. Word has length 25 [2018-06-22 15:18:20,403 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:20,404 INFO ]: With dead ends: 21 [2018-06-22 15:18:20,404 INFO ]: Without dead ends: 21 [2018-06-22 15:18:20,404 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 19 SyntacticMatches, 4 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=91, Invalid=329, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:18:20,404 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:18:20,407 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:18:20,407 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:18:20,408 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:18:20,408 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:18:20,408 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:20,408 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:18:20,408 INFO ]: Interpolant automaton has 15 states. [2018-06-22 15:18:20,408 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:18:20,409 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:18:20,409 INFO ]: Found error trace [2018-06-22 15:18:20,409 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:20,409 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:20,409 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:18:20,409 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:20,409 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:20,412 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:20,412 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:20,412 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:20,466 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:21,118 WARN ]: Spent 479.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:18:21,938 WARN ]: Spent 740.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2018-06-22 15:18:22,175 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:18:22,175 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:22,175 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:18:22,181 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:18:22,234 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:18:22,234 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:22,239 INFO ]: Computing forward predicates... [2018-06-22 15:18:23,534 WARN ]: Spent 894.00 ms on a formula simplification. DAG size of input: 180 DAG size of output: 40 [2018-06-22 15:18:23,794 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 43 [2018-06-22 15:18:24,058 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 22 [2018-06-22 15:18:24,707 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:18:24,727 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:24,727 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 15:18:24,727 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:18:24,728 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:18:24,728 INFO ]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:18:24,728 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 20 states. [2018-06-22 15:18:25,250 WARN ]: Spent 426.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 57 [2018-06-22 15:18:25,663 WARN ]: Spent 365.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 38 [2018-06-22 15:18:25,978 WARN ]: Spent 293.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 29 [2018-06-22 15:18:26,353 WARN ]: Spent 351.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 30 [2018-06-22 15:18:26,718 WARN ]: Spent 342.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 44 [2018-06-22 15:18:27,090 WARN ]: Spent 347.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 34 [2018-06-22 15:18:27,131 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:27,131 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:18:27,131 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:18:27,131 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-22 15:18:27,132 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:27,132 INFO ]: With dead ends: 23 [2018-06-22 15:18:27,132 INFO ]: Without dead ends: 23 [2018-06-22 15:18:27,133 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 21 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 97 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=141, Invalid=509, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:18:27,133 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:18:27,138 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:18:27,138 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:18:27,139 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:18:27,139 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:18:27,139 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:27,139 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:18:27,139 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:18:27,139 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:18:27,142 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:18:27,142 INFO ]: Found error trace [2018-06-22 15:18:27,142 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:27,142 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:27,142 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:18:27,142 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:27,142 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:27,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:27,143 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:27,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:27,263 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:27,687 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 18 [2018-06-22 15:18:27,920 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 24 [2018-06-22 15:18:28,267 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:18:28,267 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:28,267 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:18:28,272 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:18:28,357 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:18:28,357 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:28,361 INFO ]: Computing forward predicates... [2018-06-22 15:18:28,699 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 32 [2018-06-22 15:18:29,604 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:18:29,633 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:29,633 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 21 [2018-06-22 15:18:29,633 INFO ]: Interpolant automaton has 21 states [2018-06-22 15:18:29,633 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 15:18:29,634 INFO ]: CoverageRelationStatistics Valid=61, Invalid=359, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:18:29,634 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 21 states. [2018-06-22 15:18:30,053 WARN ]: Spent 389.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 53 [2018-06-22 15:18:30,207 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 24 [2018-06-22 15:18:30,434 WARN ]: Spent 206.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 28 [2018-06-22 15:18:30,707 WARN ]: Spent 245.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 42 [2018-06-22 15:18:30,937 WARN ]: Spent 207.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 32 [2018-06-22 15:18:31,249 WARN ]: Spent 290.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 37 [2018-06-22 15:18:31,506 WARN ]: Spent 230.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 37 [2018-06-22 15:18:31,537 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:31,537 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:18:31,538 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:18:31,538 INFO ]: Start accepts. Automaton has 21 states. Word has length 33 [2018-06-22 15:18:31,538 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:31,539 INFO ]: With dead ends: 25 [2018-06-22 15:18:31,539 INFO ]: Without dead ends: 25 [2018-06-22 15:18:31,539 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 23 SyntacticMatches, 6 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=158, Invalid=598, Unknown=0, NotChecked=0, Total=756 [2018-06-22 15:18:31,539 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:18:31,542 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:18:31,542 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:18:31,544 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:18:31,544 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:18:31,544 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:31,544 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:18:31,544 INFO ]: Interpolant automaton has 21 states. [2018-06-22 15:18:31,544 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:18:31,545 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:18:31,545 INFO ]: Found error trace [2018-06-22 15:18:31,545 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:31,545 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:31,545 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:18:31,545 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:31,545 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:31,545 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:31,545 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:31,545 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:31,619 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:32,058 WARN ]: Spent 165.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 15:18:32,527 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:18:32,528 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:32,528 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:18:32,548 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:18:32,603 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:32,609 INFO ]: Computing forward predicates... [2018-06-22 15:18:32,892 WARN ]: Spent 201.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 25 [2018-06-22 15:18:33,060 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 34 [2018-06-22 15:18:33,273 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 32 [2018-06-22 15:18:33,844 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:18:33,864 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:33,864 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 24 [2018-06-22 15:18:33,864 INFO ]: Interpolant automaton has 24 states [2018-06-22 15:18:33,864 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 15:18:33,865 INFO ]: CoverageRelationStatistics Valid=67, Invalid=485, Unknown=0, NotChecked=0, Total=552 [2018-06-22 15:18:33,865 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 24 states. [2018-06-22 15:18:34,405 WARN ]: Spent 488.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 68 [2018-06-22 15:18:34,613 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 29 [2018-06-22 15:18:34,855 WARN ]: Spent 216.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 33 [2018-06-22 15:18:35,148 WARN ]: Spent 250.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 38 [2018-06-22 15:18:35,442 WARN ]: Spent 268.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 44 [2018-06-22 15:18:35,714 WARN ]: Spent 243.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 36 [2018-06-22 15:18:36,009 WARN ]: Spent 268.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 43 [2018-06-22 15:18:36,491 WARN ]: Spent 445.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 61 [2018-06-22 15:18:36,523 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:36,523 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:18:36,524 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:18:36,524 INFO ]: Start accepts. Automaton has 24 states. Word has length 37 [2018-06-22 15:18:36,524 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:36,525 INFO ]: With dead ends: 27 [2018-06-22 15:18:36,525 INFO ]: Without dead ends: 27 [2018-06-22 15:18:36,525 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 27 SyntacticMatches, 5 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 144 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=204, Invalid=852, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 15:18:36,525 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:18:36,529 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:18:36,529 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:18:36,530 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:18:36,530 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:18:36,530 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:36,530 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:18:36,530 INFO ]: Interpolant automaton has 24 states. [2018-06-22 15:18:36,530 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:18:36,531 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:18:36,531 INFO ]: Found error trace [2018-06-22 15:18:36,531 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:36,531 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:36,531 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 15:18:36,531 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:36,531 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:36,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:36,532 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:18:36,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:36,632 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:37,749 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:18:37,749 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:37,749 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:18:37,755 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:18:37,818 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:18:37,818 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:37,824 INFO ]: Computing forward predicates... [2018-06-22 15:18:38,080 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 22 [2018-06-22 15:18:38,426 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 25 [2018-06-22 15:18:38,694 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 32 [2018-06-22 15:18:38,856 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 39 [2018-06-22 15:18:39,046 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 25 [2018-06-22 15:18:41,300 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:18:41,319 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:41,319 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 35 [2018-06-22 15:18:41,320 INFO ]: Interpolant automaton has 35 states [2018-06-22 15:18:41,320 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 15:18:41,320 INFO ]: CoverageRelationStatistics Valid=112, Invalid=1078, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 15:18:41,320 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 35 states. [2018-06-22 15:18:42,100 WARN ]: Spent 697.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 92 [2018-06-22 15:18:42,375 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 29 [2018-06-22 15:18:42,834 WARN ]: Spent 420.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 42 [2018-06-22 15:18:43,363 WARN ]: Spent 489.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 53 [2018-06-22 15:18:43,956 WARN ]: Spent 553.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 53 [2018-06-22 15:18:44,523 WARN ]: Spent 469.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 43 [2018-06-22 15:18:45,139 WARN ]: Spent 565.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 57 [2018-06-22 15:18:45,576 WARN ]: Spent 394.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 41 [2018-06-22 15:18:46,209 WARN ]: Spent 577.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 63 [2018-06-22 15:18:46,254 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:46,254 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:18:46,254 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:18:46,254 INFO ]: Start accepts. Automaton has 35 states. Word has length 41 [2018-06-22 15:18:46,254 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:46,255 INFO ]: With dead ends: 29 [2018-06-22 15:18:46,255 INFO ]: Without dead ends: 29 [2018-06-22 15:18:46,256 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 26 SyntacticMatches, 1 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 272 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=306, Invalid=1674, Unknown=0, NotChecked=0, Total=1980 [2018-06-22 15:18:46,256 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:18:46,261 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:18:46,264 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:18:46,265 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:18:46,265 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:18:46,265 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:46,265 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:18:46,265 INFO ]: Interpolant automaton has 35 states. [2018-06-22 15:18:46,265 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:18:46,266 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:18:46,266 INFO ]: Found error trace [2018-06-22 15:18:46,266 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:46,266 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:46,266 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 15:18:46,266 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:46,266 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:46,267 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:46,267 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:46,267 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:46,365 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:47,434 WARN ]: Spent 763.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 20 [2018-06-22 15:18:47,824 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 26 [2018-06-22 15:18:48,278 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:18:48,278 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:48,278 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:18:48,283 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:18:48,361 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:18:48,361 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:48,378 INFO ]: Computing forward predicates... [2018-06-22 15:18:48,588 WARN ]: Spent 161.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 26 [2018-06-22 15:18:48,987 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 25 [2018-06-22 15:18:50,336 WARN ]: Spent 587.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 39 [2018-06-22 15:18:50,479 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 25 [2018-06-22 15:18:51,687 INFO ]: Checked inductivity of 171 backedges. 2 proven. 124 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:18:51,706 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:51,706 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 40 [2018-06-22 15:18:51,707 INFO ]: Interpolant automaton has 40 states [2018-06-22 15:18:51,707 INFO ]: Constructing interpolant automaton starting with 40 interpolants. [2018-06-22 15:18:51,708 INFO ]: CoverageRelationStatistics Valid=138, Invalid=1422, Unknown=0, NotChecked=0, Total=1560 [2018-06-22 15:18:51,708 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 40 states. [2018-06-22 15:18:52,643 WARN ]: Spent 842.00 ms on a formula simplification. DAG size of input: 139 DAG size of output: 108 [2018-06-22 15:18:52,969 WARN ]: Spent 243.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 38 [2018-06-22 15:18:53,427 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 53 [2018-06-22 15:18:53,959 WARN ]: Spent 485.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 58 [2018-06-22 15:18:54,327 WARN ]: Spent 321.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 68 [2018-06-22 15:18:54,742 WARN ]: Spent 368.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 44 [2018-06-22 15:18:55,240 WARN ]: Spent 451.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 52 [2018-06-22 15:18:55,701 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 51 [2018-06-22 15:18:56,201 WARN ]: Spent 451.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 56 [2018-06-22 15:18:56,844 WARN ]: Spent 584.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 78 [2018-06-22 15:18:56,894 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:56,894 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:18:56,897 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:18:56,897 INFO ]: Start accepts. Automaton has 40 states. Word has length 45 [2018-06-22 15:18:56,897 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:56,898 INFO ]: With dead ends: 31 [2018-06-22 15:18:56,898 INFO ]: Without dead ends: 31 [2018-06-22 15:18:56,899 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 367 ImplicationChecksByTransitivity, 9.2s TimeCoverageRelationStatistics Valid=392, Invalid=2158, Unknown=0, NotChecked=0, Total=2550 [2018-06-22 15:18:56,899 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:18:56,907 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:18:56,907 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:18:56,907 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:18:56,907 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:18:56,907 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:56,907 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:18:56,907 INFO ]: Interpolant automaton has 40 states. [2018-06-22 15:18:56,908 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:18:56,909 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:18:56,909 INFO ]: Found error trace [2018-06-22 15:18:56,909 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:56,909 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:56,909 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-22 15:18:56,909 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:56,909 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:56,910 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:56,910 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:56,910 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:56,992 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:57,216 WARN ]: Spent 101.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 15:18:57,582 WARN ]: Spent 316.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 15:18:58,224 INFO ]: Checked inductivity of 210 backedges. 1 proven. 154 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:18:58,225 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:58,284 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:18:58,290 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:18:58,364 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:18:58,364 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:58,371 INFO ]: Computing forward predicates... [2018-06-22 15:18:58,708 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 32 [2018-06-22 15:18:58,928 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 27 [2018-06-22 15:18:59,134 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 32 [2018-06-22 15:18:59,315 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 39 [2018-06-22 15:19:00,145 WARN ]: Spent 718.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 44 [2018-06-22 15:19:01,137 INFO ]: Checked inductivity of 210 backedges. 3 proven. 152 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:19:01,156 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:19:01,156 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 37 [2018-06-22 15:19:01,157 INFO ]: Interpolant automaton has 37 states [2018-06-22 15:19:01,157 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-22 15:19:01,158 INFO ]: CoverageRelationStatistics Valid=146, Invalid=1186, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 15:19:01,158 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 37 states. [2018-06-22 15:19:01,858 WARN ]: Spent 645.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 68 [2018-06-22 15:19:02,229 WARN ]: Spent 265.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 36 [2018-06-22 15:19:02,570 WARN ]: Spent 302.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 35 [2018-06-22 15:19:03,030 WARN ]: Spent 427.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 40 [2018-06-22 15:19:03,523 WARN ]: Spent 461.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 40 [2018-06-22 15:19:03,866 WARN ]: Spent 311.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 34 [2018-06-22 15:19:04,458 WARN ]: Spent 560.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 44 [2018-06-22 15:19:04,759 WARN ]: Spent 268.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 33 [2018-06-22 15:19:05,218 WARN ]: Spent 430.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 41 [2018-06-22 15:19:05,824 WARN ]: Spent 576.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 39 [2018-06-22 15:19:06,494 WARN ]: Spent 626.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 66 [2018-06-22 15:19:06,606 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:19:06,606 INFO ]: Finished difference Result 33 states and 34 transitions. [2018-06-22 15:19:06,607 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 15:19:06,607 INFO ]: Start accepts. Automaton has 37 states. Word has length 49 [2018-06-22 15:19:06,607 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:19:06,607 INFO ]: With dead ends: 33 [2018-06-22 15:19:06,607 INFO ]: Without dead ends: 33 [2018-06-22 15:19:06,608 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 33 SyntacticMatches, 4 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 409 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=416, Invalid=1840, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 15:19:06,608 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 15:19:06,612 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-22 15:19:06,612 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-22 15:19:06,612 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 34 transitions. [2018-06-22 15:19:06,613 INFO ]: Start accepts. Automaton has 33 states and 34 transitions. Word has length 49 [2018-06-22 15:19:06,613 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:19:06,613 INFO ]: Abstraction has 33 states and 34 transitions. [2018-06-22 15:19:06,613 INFO ]: Interpolant automaton has 37 states. [2018-06-22 15:19:06,613 INFO ]: Start isEmpty. Operand 33 states and 34 transitions. [2018-06-22 15:19:06,614 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 15:19:06,614 INFO ]: Found error trace [2018-06-22 15:19:06,614 INFO ]: trace histogram [12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:19:06,614 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:19:06,614 INFO ]: Analyzing trace with hash 1955719355, now seen corresponding path program 11 times [2018-06-22 15:19:06,614 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:19:06,614 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:19:06,614 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:19:06,614 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:19:06,614 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:19:06,737 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:19:07,805 WARN ]: Spent 782.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 16 [2018-06-22 15:19:08,175 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 40 Received shutdown request... [2018-06-22 15:19:08,796 WARN ]: Verification canceled [2018-06-22 15:19:08,800 WARN ]: Timeout [2018-06-22 15:19:08,800 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:19:08 BoogieIcfgContainer [2018-06-22 15:19:08,800 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:19:08,801 INFO ]: Toolchain (without parser) took 59874.91 ms. Allocated memory was 307.8 MB in the beginning and 789.1 MB in the end (delta: 481.3 MB). Free memory was 257.2 MB in the beginning and 318.2 MB in the end (delta: -61.1 MB). Peak memory consumption was 420.2 MB. Max. memory is 3.6 GB. [2018-06-22 15:19:08,801 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 307.8 MB. Free memory is still 271.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:19:08,801 INFO ]: ChcToBoogie took 50.33 ms. Allocated memory is still 307.8 MB. Free memory was 257.2 MB in the beginning and 255.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:19:08,802 INFO ]: Boogie Preprocessor took 43.23 ms. Allocated memory is still 307.8 MB. Free memory was 255.2 MB in the beginning and 254.1 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:19:08,802 INFO ]: RCFGBuilder took 203.62 ms. Allocated memory is still 307.8 MB. Free memory was 254.1 MB in the beginning and 244.1 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:19:08,803 INFO ]: TraceAbstraction took 59569.27 ms. Allocated memory was 307.8 MB in the beginning and 789.1 MB in the end (delta: 481.3 MB). Free memory was 244.1 MB in the beginning and 318.2 MB in the end (delta: -74.2 MB). Peak memory consumption was 407.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:19:08,805 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 307.8 MB. Free memory is still 271.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 50.33 ms. Allocated memory is still 307.8 MB. Free memory was 257.2 MB in the beginning and 255.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 43.23 ms. Allocated memory is still 307.8 MB. Free memory was 255.2 MB in the beginning and 254.1 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 203.62 ms. Allocated memory is still 307.8 MB. Free memory was 254.1 MB in the beginning and 244.1 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 59569.27 ms. Allocated memory was 307.8 MB in the beginning and 789.1 MB in the end (delta: 481.3 MB). Free memory was 244.1 MB in the beginning and 318.2 MB in the end (delta: -74.2 MB). Peak memory consumption was 407.1 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 InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateComparison was comparing new predicate (quantifier-free) to 19 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 59.4s OverallTime, 12 OverallIterations, 12 TraceHistogramMax, 25.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 152 SDtfs, 652 SDslu, 1187 SDs, 0 SdLazy, 1046 SolverSat, 772 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 525 GetRequests, 221 SyntacticMatches, 25 SemanticMatches, 279 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1537 ImplicationChecksByTransitivity, 45.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.2s SatisfiabilityAnalysisTime, 29.6s InterpolantComputationTime, 629 NumberOfCodeBlocks, 629 NumberOfCodeBlocksAsserted, 46 NumberOfCheckSat, 608 ConstructedInterpolants, 0 QuantifiedInterpolants, 650788 SizeOfPredicates, 973 NumberOfNonLiveVariables, 2865 ConjunctsInSsa, 541 ConjunctsInUnsatCore, 21 InterpolantComputations, 1 PerfectInterpolantSequences, 446/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/nested9.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-19-08-814.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nested9.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-19-08-814.csv Completed graceful shutdown