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/pldi082_unbounded.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:26:57,813 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:26:57,815 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:26:57,832 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:26:57,832 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:26:57,833 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:26:57,834 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:26:57,841 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:26:57,843 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:26:57,844 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:26:57,844 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:26:57,846 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:26:57,847 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:26:57,848 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:26:57,849 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:26:57,852 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:26:57,854 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:26:57,855 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:26:57,868 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:26:57,869 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:26:57,870 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:26:57,872 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:26:57,872 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:26:57,872 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:26:57,873 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:26:57,874 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:26:57,874 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:26:57,875 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:26:57,876 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:26:57,881 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:26:57,882 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:26:57,882 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:26:57,882 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:26:57,883 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:26:57,883 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:26:57,884 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:26:57,903 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:26:57,905 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:26:57,905 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:26:57,905 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:26:57,906 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:26:57,906 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:26:57,907 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:26:57,907 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:26:57,907 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:26:57,907 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:26:57,908 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:26:57,908 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:26:57,908 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:26:57,908 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:26:57,908 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:26:57,908 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:26:57,909 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:26:57,909 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:26:57,910 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:26:57,911 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:26:57,911 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:26:57,954 INFO ]: Repository-Root is: /tmp [2018-06-22 15:26:57,970 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:26:57,974 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:26:57,975 INFO ]: Initializing SmtParser... [2018-06-22 15:26:57,975 INFO ]: SmtParser initialized [2018-06-22 15:26:57,976 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/pldi082_unbounded.c.smt2 [2018-06-22 15:26:57,977 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:26:58,060 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/pldi082_unbounded.c.smt2 unknown [2018-06-22 15:26:58,298 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/pldi082_unbounded.c.smt2 [2018-06-22 15:26:58,305 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:26:58,311 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:26:58,311 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:26:58,311 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:26:58,311 INFO ]: ChcToBoogie initialized [2018-06-22 15:26:58,315 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:26:58" (1/1) ... [2018-06-22 15:26:58,360 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58 Unit [2018-06-22 15:26:58,360 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:26:58,361 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:26:58,361 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:26:58,361 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:26:58,382 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (1/1) ... [2018-06-22 15:26:58,382 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (1/1) ... [2018-06-22 15:26:58,391 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (1/1) ... [2018-06-22 15:26:58,394 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (1/1) ... [2018-06-22 15:26:58,398 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (1/1) ... [2018-06-22 15:26:58,399 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (1/1) ... [2018-06-22 15:26:58,400 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (1/1) ... [2018-06-22 15:26:58,402 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:26:58,402 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:26:58,402 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:26:58,402 INFO ]: RCFGBuilder initialized [2018-06-22 15:26:58,403 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (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:26:58,418 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:26:58,418 INFO ]: Found specification of procedure False [2018-06-22 15:26:58,419 INFO ]: Found implementation of procedure False [2018-06-22 15:26:58,419 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:26:58,419 INFO ]: Found specification of procedure state [2018-06-22 15:26:58,419 INFO ]: Found implementation of procedure state [2018-06-22 15:26:58,419 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:26:58,419 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:26:58,419 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:26:58,674 INFO ]: Using library mode [2018-06-22 15:26:58,675 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:26:58 BoogieIcfgContainer [2018-06-22 15:26:58,675 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:26:58,676 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:26:58,677 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:26:58,679 INFO ]: TraceAbstraction initialized [2018-06-22 15:26:58,680 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:26:58" (1/3) ... [2018-06-22 15:26:58,680 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7cd57589 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:26:58, skipping insertion in model container [2018-06-22 15:26:58,680 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:26:58" (2/3) ... [2018-06-22 15:26:58,681 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7cd57589 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:26:58, skipping insertion in model container [2018-06-22 15:26:58,681 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:26:58" (3/3) ... [2018-06-22 15:26:58,682 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:26:58,691 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:26:58,698 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:26:58,741 INFO ]: Using default assertion order modulation [2018-06-22 15:26:58,741 INFO ]: Interprodecural is true [2018-06-22 15:26:58,741 INFO ]: Hoare is false [2018-06-22 15:26:58,742 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:26:58,742 INFO ]: Backedges is TWOTRACK [2018-06-22 15:26:58,742 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:26:58,742 INFO ]: Difference is false [2018-06-22 15:26:58,742 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:26:58,742 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:26:58,755 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:26:58,764 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:26:58,764 INFO ]: Found error trace [2018-06-22 15:26:58,765 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:58,765 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:58,769 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:26:58,771 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:58,771 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:58,805 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:58,806 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:26:58,806 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:58,832 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:58,960 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:26:58,963 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:26:58,963 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:26:58,965 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:26:58,976 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:26:58,977 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:26:58,979 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:26:59,064 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:59,064 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:26:59,065 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:26:59,066 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:26:59,067 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:59,080 INFO ]: With dead ends: 13 [2018-06-22 15:26:59,080 INFO ]: Without dead ends: 13 [2018-06-22 15:26:59,082 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:26:59,097 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:26:59,116 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:26:59,116 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:26:59,117 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:26:59,118 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:26:59,118 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:59,118 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:26:59,118 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:26:59,118 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:26:59,119 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:26:59,119 INFO ]: Found error trace [2018-06-22 15:26:59,119 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:59,119 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:59,119 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:26:59,119 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:59,119 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:59,120 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:59,120 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:26:59,120 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:59,166 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:59,371 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:26:59,371 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:26:59,371 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:26:59,379 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:26:59,420 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:26:59,429 INFO ]: Computing forward predicates... [2018-06-22 15:26:59,715 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:26:59,748 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:26:59,748 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 15:26:59,748 INFO ]: Interpolant automaton has 6 states [2018-06-22 15:26:59,749 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 15:26:59,749 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:26:59,749 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-22 15:26:59,925 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:26:59,925 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:26:59,926 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:26:59,926 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 15:26:59,926 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:26:59,927 INFO ]: With dead ends: 15 [2018-06-22 15:26:59,927 INFO ]: Without dead ends: 15 [2018-06-22 15:26:59,927 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:26:59,928 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:26:59,930 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:26:59,930 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:26:59,932 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:26:59,932 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:26:59,932 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:26:59,932 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:26:59,932 INFO ]: Interpolant automaton has 6 states. [2018-06-22 15:26:59,932 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:26:59,933 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:26:59,933 INFO ]: Found error trace [2018-06-22 15:26:59,933 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:26:59,933 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:26:59,933 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:26:59,933 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:26:59,933 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:26:59,934 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:59,934 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:26:59,934 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:26:59,987 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:00,243 WARN ]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 15:27:00,424 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:27:00,424 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:00,424 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:27:00,441 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:27:00,497 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:27:00,497 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:00,500 INFO ]: Computing forward predicates... [2018-06-22 15:27:00,919 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:27:00,952 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:27:00,952 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-22 15:27:00,952 INFO ]: Interpolant automaton has 10 states [2018-06-22 15:27:00,952 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 15:27:00,952 INFO ]: CoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:27:00,953 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 10 states. [2018-06-22 15:27:01,263 WARN ]: Spent 130.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 15:27:01,409 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 18 [2018-06-22 15:27:01,430 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:27:01,430 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:27:01,431 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:27:01,431 INFO ]: Start accepts. Automaton has 10 states. Word has length 17 [2018-06-22 15:27:01,431 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:27:01,432 INFO ]: With dead ends: 17 [2018-06-22 15:27:01,432 INFO ]: Without dead ends: 17 [2018-06-22 15:27:01,432 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:27:01,432 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:27:01,435 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:27:01,435 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:27:01,436 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:27:01,436 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:27:01,436 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:27:01,436 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:27:01,436 INFO ]: Interpolant automaton has 10 states. [2018-06-22 15:27:01,436 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:27:01,437 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:27:01,437 INFO ]: Found error trace [2018-06-22 15:27:01,437 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:27:01,437 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:27:01,437 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:27:01,437 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:27:01,437 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:27:01,438 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:01,438 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:27:01,438 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:01,472 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:01,763 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:27:01,764 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:01,764 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:27:01,783 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:27:01,861 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:27:01,861 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:01,866 INFO ]: Computing forward predicates... [2018-06-22 15:27:02,077 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:27:02,100 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:27:02,100 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-22 15:27:02,100 INFO ]: Interpolant automaton has 10 states [2018-06-22 15:27:02,100 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 15:27:02,100 INFO ]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:27:02,101 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 10 states. [2018-06-22 15:27:02,473 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:27:02,473 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:27:02,474 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:27:02,474 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-22 15:27:02,474 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:27:02,474 INFO ]: With dead ends: 19 [2018-06-22 15:27:02,475 INFO ]: Without dead ends: 19 [2018-06-22 15:27:02,475 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:27:02,475 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:27:02,478 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:27:02,478 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:27:02,479 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:27:02,479 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:27:02,479 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:27:02,479 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:27:02,479 INFO ]: Interpolant automaton has 10 states. [2018-06-22 15:27:02,479 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:27:02,479 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:27:02,480 INFO ]: Found error trace [2018-06-22 15:27:02,480 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:27:02,480 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:27:02,480 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:27:02,480 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:27:02,480 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:27:02,481 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:02,481 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:27:02,481 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:02,512 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:02,939 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:27:02,939 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:02,939 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:27:02,944 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:27:02,995 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:27:02,995 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:03,001 INFO ]: Computing forward predicates... [2018-06-22 15:27:03,707 WARN ]: Spent 487.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 16 [2018-06-22 15:27:04,034 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:27:04,054 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:27:04,054 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 13 [2018-06-22 15:27:04,054 INFO ]: Interpolant automaton has 13 states [2018-06-22 15:27:04,054 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 15:27:04,054 INFO ]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2018-06-22 15:27:04,055 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 13 states. [2018-06-22 15:27:04,237 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 38 [2018-06-22 15:27:04,711 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 38 [2018-06-22 15:27:04,729 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:27:04,730 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:27:04,731 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:27:04,731 INFO ]: Start accepts. Automaton has 13 states. Word has length 25 [2018-06-22 15:27:04,731 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:27:04,732 INFO ]: With dead ends: 21 [2018-06-22 15:27:04,732 INFO ]: Without dead ends: 21 [2018-06-22 15:27:04,732 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 22 SyntacticMatches, 3 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=81, Invalid=225, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:27:04,732 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:27:04,735 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:27:04,735 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:27:04,736 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:27:04,736 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:27:04,736 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:27:04,736 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:27:04,736 INFO ]: Interpolant automaton has 13 states. [2018-06-22 15:27:04,736 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:27:04,737 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:27:04,737 INFO ]: Found error trace [2018-06-22 15:27:04,737 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:27:04,737 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:27:04,737 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:27:04,738 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:27:04,738 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:27:04,738 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:04,738 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:27:04,738 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:04,775 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:05,030 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 15:27:05,359 WARN ]: Spent 278.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-06-22 15:27:05,592 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:27:05,592 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:05,592 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:27:05,598 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:27:05,640 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:27:05,640 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:05,644 INFO ]: Computing forward predicates... [2018-06-22 15:27:11,245 WARN ]: Spent 4.95 s on a formula simplification. DAG size of input: 445 DAG size of output: 84 [2018-06-22 15:27:12,500 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:27:12,520 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:27:12,520 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 18 [2018-06-22 15:27:12,520 INFO ]: Interpolant automaton has 18 states [2018-06-22 15:27:12,520 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 15:27:12,520 INFO ]: CoverageRelationStatistics Valid=44, Invalid=262, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:27:12,520 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 18 states. [2018-06-22 15:27:13,431 WARN ]: Spent 881.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 69 [2018-06-22 15:27:13,743 WARN ]: Spent 254.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 34 [2018-06-22 15:27:14,498 WARN ]: Spent 605.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 28 [2018-06-22 15:27:14,967 WARN ]: Spent 435.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 44 [2018-06-22 15:27:15,488 WARN ]: Spent 438.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 48 [2018-06-22 15:27:16,042 WARN ]: Spent 522.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 56 [2018-06-22 15:27:16,070 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:27:16,070 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:27:16,073 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:27:16,073 INFO ]: Start accepts. Automaton has 18 states. Word has length 29 [2018-06-22 15:27:16,073 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:27:16,073 INFO ]: With dead ends: 23 [2018-06-22 15:27:16,073 INFO ]: Without dead ends: 23 [2018-06-22 15:27:16,074 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 24 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 9.7s TimeCoverageRelationStatistics Valid=113, Invalid=439, Unknown=0, NotChecked=0, Total=552 [2018-06-22 15:27:16,074 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:27:16,077 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:27:16,077 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:27:16,078 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:27:16,078 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:27:16,078 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:27:16,078 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:27:16,078 INFO ]: Interpolant automaton has 18 states. [2018-06-22 15:27:16,078 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:27:16,079 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:27:16,079 INFO ]: Found error trace [2018-06-22 15:27:16,079 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:27:16,079 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:27:16,079 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:27:16,079 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:27:16,079 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:27:16,080 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:16,080 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:27:16,080 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:16,135 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:16,411 WARN ]: Spent 117.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 15:27:17,288 WARN ]: Spent 829.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-22 15:27:17,692 WARN ]: Spent 323.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 30 [2018-06-22 15:27:18,143 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:27:18,143 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:18,143 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:27:18,149 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:27:18,211 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:27:18,211 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:18,215 INFO ]: Computing forward predicates... [2018-06-22 15:27:18,992 WARN ]: Spent 695.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 44 [2018-06-22 15:27:20,190 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:27:20,220 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:27:20,220 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 21 [2018-06-22 15:27:20,220 INFO ]: Interpolant automaton has 21 states [2018-06-22 15:27:20,221 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 15:27:20,221 INFO ]: CoverageRelationStatistics Valid=54, Invalid=366, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:27:20,221 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 21 states. [2018-06-22 15:27:20,924 WARN ]: Spent 657.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 68 [2018-06-22 15:27:21,146 WARN ]: Spent 173.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 24 [2018-06-22 15:27:21,375 WARN ]: Spent 201.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 28 [2018-06-22 15:27:21,716 WARN ]: Spent 316.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 51 [2018-06-22 15:27:22,169 WARN ]: Spent 423.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 51 [2018-06-22 15:27:22,794 WARN ]: Spent 480.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 54 [2018-06-22 15:27:23,233 WARN ]: Spent 399.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 54 [2018-06-22 15:27:23,262 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:27:23,262 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:27:23,262 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:27:23,262 INFO ]: Start accepts. Automaton has 21 states. Word has length 33 [2018-06-22 15:27:23,263 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:27:23,263 INFO ]: With dead ends: 25 [2018-06-22 15:27:23,263 INFO ]: Without dead ends: 25 [2018-06-22 15:27:23,264 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 26 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 93 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=150, Invalid=606, Unknown=0, NotChecked=0, Total=756 [2018-06-22 15:27:23,264 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:27:23,266 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:27:23,266 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:27:23,266 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:27:23,267 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:27:23,267 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:27:23,267 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:27:23,267 INFO ]: Interpolant automaton has 21 states. [2018-06-22 15:27:23,267 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:27:23,268 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:27:23,268 INFO ]: Found error trace [2018-06-22 15:27:23,268 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:27:23,268 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:27:23,268 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:27:23,268 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:27:23,268 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:27:23,269 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:23,269 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:27:23,269 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:23,340 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:24,151 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:27:24,151 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:24,151 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:27:24,157 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:27:24,205 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:24,212 INFO ]: Computing forward predicates... [2018-06-22 15:27:24,654 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 29 [2018-06-22 15:27:25,941 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:27:25,961 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:27:25,961 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 33 [2018-06-22 15:27:25,961 INFO ]: Interpolant automaton has 33 states [2018-06-22 15:27:25,961 INFO ]: Constructing interpolant automaton starting with 33 interpolants. [2018-06-22 15:27:25,962 INFO ]: CoverageRelationStatistics Valid=101, Invalid=955, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 15:27:25,962 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 33 states. [2018-06-22 15:27:26,717 WARN ]: Spent 685.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 90 [2018-06-22 15:27:26,929 WARN ]: Spent 164.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 32 [2018-06-22 15:27:27,172 WARN ]: Spent 169.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 49 [2018-06-22 15:27:27,466 WARN ]: Spent 244.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 55 [2018-06-22 15:27:27,850 WARN ]: Spent 347.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 58 [2018-06-22 15:27:28,251 WARN ]: Spent 364.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 59 [2018-06-22 15:27:28,572 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 51 [2018-06-22 15:27:29,066 WARN ]: Spent 409.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 63 [2018-06-22 15:27:29,109 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:27:29,109 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:27:29,110 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:27:29,110 INFO ]: Start accepts. Automaton has 33 states. Word has length 37 [2018-06-22 15:27:29,110 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:27:29,110 INFO ]: With dead ends: 27 [2018-06-22 15:27:29,110 INFO ]: Without dead ends: 27 [2018-06-22 15:27:29,111 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 232 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=257, Invalid=1383, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:27:29,111 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:27:29,115 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:27:29,115 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:27:29,116 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:27:29,116 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:27:29,116 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:27:29,116 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:27:29,116 INFO ]: Interpolant automaton has 33 states. [2018-06-22 15:27:29,116 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:27:29,117 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:27:29,117 INFO ]: Found error trace [2018-06-22 15:27:29,117 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:27:29,117 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:27:29,117 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 15:27:29,117 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:27:29,117 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:27:29,118 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:29,118 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:27:29,118 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:29,181 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:30,102 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:27:30,102 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:30,102 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:27:30,109 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:27:30,177 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:27:30,177 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:30,182 INFO ]: Computing forward predicates... [2018-06-22 15:27:34,475 WARN ]: Spent 3.86 s on a formula simplification. DAG size of input: 622 DAG size of output: 63 [2018-06-22 15:27:34,692 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 30 [2018-06-22 15:27:35,146 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 35 [2018-06-22 15:27:35,432 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 29 [2018-06-22 15:27:38,744 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:27:38,764 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:27:38,764 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 37 [2018-06-22 15:27:38,764 INFO ]: Interpolant automaton has 37 states [2018-06-22 15:27:38,764 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-22 15:27:38,765 INFO ]: CoverageRelationStatistics Valid=106, Invalid=1226, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 15:27:38,765 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 37 states. [2018-06-22 15:27:40,018 WARN ]: Spent 1.15 s on a formula simplification. DAG size of input: 181 DAG size of output: 130 [2018-06-22 15:27:40,451 WARN ]: Spent 350.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 33 [2018-06-22 15:27:40,846 WARN ]: Spent 339.00 ms on a formula simplification. DAG size of input: 184 DAG size of output: 44 [2018-06-22 15:27:41,572 WARN ]: Spent 629.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 55 [2018-06-22 15:27:42,517 WARN ]: Spent 876.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 80 [2018-06-22 15:27:43,280 WARN ]: Spent 711.00 ms on a formula simplification. DAG size of input: 186 DAG size of output: 61 [2018-06-22 15:27:43,947 WARN ]: Spent 615.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 70 [2018-06-22 15:27:44,541 WARN ]: Spent 506.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 50 [2018-06-22 15:27:45,494 WARN ]: Spent 902.00 ms on a formula simplification. DAG size of input: 174 DAG size of output: 86 [2018-06-22 15:27:45,546 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:27:45,546 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:27:45,547 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:27:45,547 INFO ]: Start accepts. Automaton has 37 states. Word has length 41 [2018-06-22 15:27:45,547 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:27:45,548 INFO ]: With dead ends: 29 [2018-06-22 15:27:45,548 INFO ]: Without dead ends: 29 [2018-06-22 15:27:45,548 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 269 ImplicationChecksByTransitivity, 13.5s TimeCoverageRelationStatistics Valid=304, Invalid=1858, Unknown=0, NotChecked=0, Total=2162 [2018-06-22 15:27:45,548 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:27:45,552 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:27:45,552 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:27:45,553 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:27:45,553 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:27:45,553 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:27:45,553 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:27:45,553 INFO ]: Interpolant automaton has 37 states. [2018-06-22 15:27:45,553 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:27:45,554 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:27:45,554 INFO ]: Found error trace [2018-06-22 15:27:45,554 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:27:45,554 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:27:45,554 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 15:27:45,554 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:27:45,554 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:27:45,555 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:45,555 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:27:45,555 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:45,613 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:46,461 WARN ]: Spent 544.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 20 [2018-06-22 15:27:46,764 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 35 [2018-06-22 15:27:46,939 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 36 [2018-06-22 15:27:47,054 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 36 [2018-06-22 15:27:47,820 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:27:47,820 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:47,820 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:27:47,838 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:27:47,915 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:27:47,915 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:47,937 INFO ]: Computing forward predicates... [2018-06-22 15:27:48,229 WARN ]: Spent 197.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 10 [2018-06-22 15:27:48,868 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 29 [2018-06-22 15:27:50,220 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:27:50,240 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:27:50,240 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 41 [2018-06-22 15:27:50,240 INFO ]: Interpolant automaton has 41 states [2018-06-22 15:27:50,240 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 15:27:50,241 INFO ]: CoverageRelationStatistics Valid=117, Invalid=1523, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:27:50,241 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 41 states. [2018-06-22 15:27:51,294 WARN ]: Spent 970.00 ms on a formula simplification. DAG size of input: 145 DAG size of output: 112 [2018-06-22 15:27:51,525 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 34 [2018-06-22 15:27:51,880 WARN ]: Spent 303.00 ms on a formula simplification. DAG size of input: 148 DAG size of output: 54 [2018-06-22 15:27:52,283 WARN ]: Spent 353.00 ms on a formula simplification. DAG size of input: 138 DAG size of output: 56 [2018-06-22 15:27:52,709 WARN ]: Spent 371.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 60 [2018-06-22 15:27:53,265 WARN ]: Spent 504.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 62 [2018-06-22 15:27:53,533 WARN ]: Spent 217.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 50 [2018-06-22 15:27:53,931 WARN ]: Spent 345.00 ms on a formula simplification. DAG size of input: 136 DAG size of output: 52 [2018-06-22 15:27:54,311 WARN ]: Spent 331.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 55 [2018-06-22 15:27:54,988 WARN ]: Spent 618.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 77 [2018-06-22 15:27:55,040 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:27:55,040 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:27:55,043 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:27:55,043 INFO ]: Start accepts. Automaton has 41 states. Word has length 45 [2018-06-22 15:27:55,044 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:27:55,044 INFO ]: With dead ends: 31 [2018-06-22 15:27:55,044 INFO ]: Without dead ends: 31 [2018-06-22 15:27:55,045 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 292 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=355, Invalid=2195, Unknown=0, NotChecked=0, Total=2550 [2018-06-22 15:27:55,045 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:27:55,052 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:27:55,052 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:27:55,053 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:27:55,053 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:27:55,053 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:27:55,053 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:27:55,053 INFO ]: Interpolant automaton has 41 states. [2018-06-22 15:27:55,053 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:27:55,054 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:27:55,054 INFO ]: Found error trace [2018-06-22 15:27:55,054 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:27:55,054 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:27:55,054 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-22 15:27:55,054 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:27:55,054 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:27:55,058 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:55,058 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:27:55,058 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:27:55,123 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:55,596 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 45 [2018-06-22 15:27:55,719 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 41 [2018-06-22 15:27:55,890 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 33 [2018-06-22 15:27:56,503 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:27:56,504 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:27:56,504 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:27:56,510 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:27:56,595 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:27:56,595 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:27:56,606 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:27:59,043 WARN ]: Removed 6 from assertion stack [2018-06-22 15:27:59,043 INFO ]: Timeout while computing interpolants [2018-06-22 15:27:59,244 WARN ]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:27:59,244 WARN ]: Verification canceled [2018-06-22 15:27:59,247 WARN ]: Timeout [2018-06-22 15:27:59,247 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:27:59 BoogieIcfgContainer [2018-06-22 15:27:59,247 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:27:59,248 INFO ]: Toolchain (without parser) took 60942.70 ms. Allocated memory was 309.9 MB in the beginning and 764.4 MB in the end (delta: 454.6 MB). Free memory was 262.3 MB in the beginning and 316.8 MB in the end (delta: -54.5 MB). Peak memory consumption was 542.7 MB. Max. memory is 3.6 GB. [2018-06-22 15:27:59,248 INFO ]: SmtParser took 0.05 ms. Allocated memory is still 309.9 MB. Free memory is still 274.4 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:27:59,249 INFO ]: ChcToBoogie took 49.81 ms. Allocated memory is still 309.9 MB. Free memory was 262.3 MB in the beginning and 260.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:27:59,249 INFO ]: Boogie Preprocessor took 40.68 ms. Allocated memory is still 309.9 MB. Free memory was 260.3 MB in the beginning and 258.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:27:59,249 INFO ]: RCFGBuilder took 272.58 ms. Allocated memory is still 309.9 MB. Free memory was 258.3 MB in the beginning and 248.2 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:27:59,250 INFO ]: TraceAbstraction took 60570.74 ms. Allocated memory was 309.9 MB in the beginning and 764.4 MB in the end (delta: 454.6 MB). Free memory was 248.2 MB in the beginning and 316.8 MB in the end (delta: -68.6 MB). Peak memory consumption was 528.7 MB. Max. memory is 3.6 GB. [2018-06-22 15:27:59,252 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.05 ms. Allocated memory is still 309.9 MB. Free memory is still 274.4 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 49.81 ms. Allocated memory is still 309.9 MB. Free memory was 262.3 MB in the beginning and 260.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 40.68 ms. Allocated memory is still 309.9 MB. Free memory was 260.3 MB in the beginning and 258.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 272.58 ms. Allocated memory is still 309.9 MB. Free memory was 258.3 MB in the beginning and 248.2 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 60570.74 ms. Allocated memory was 309.9 MB in the beginning and 764.4 MB in the end (delta: 454.6 MB). Free memory was 248.2 MB in the beginning and 316.8 MB in the end (delta: -68.6 MB). Peak memory consumption was 528.7 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 50 with TraceHistMax 11, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 1164. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 60.5s OverallTime, 11 OverallIterations, 11 TraceHistogramMax, 23.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 139 SDtfs, 577 SDslu, 1037 SDs, 0 SdLazy, 934 SolverSat, 656 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 434 GetRequests, 199 SyntacticMatches, 10 SemanticMatches, 225 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 974 ImplicationChecksByTransitivity, 44.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=31occurred in iteration=10, 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, 10 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 31.6s InterpolantComputationTime, 531 NumberOfCodeBlocks, 531 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 512 ConstructedInterpolants, 0 QuantifiedInterpolants, 1462676 SizeOfPredicates, 492 NumberOfNonLiveVariables, 2412 ConjunctsInSsa, 459 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 330/1230 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/pldi082_unbounded.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-27-59-262.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/pldi082_unbounded.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-27-59-262.csv Completed graceful shutdown