java -Xss4m -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_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:16:04,933 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:16:04,935 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:16:04,946 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:16:04,947 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:16:04,948 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:16:04,949 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:16:04,950 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:16:04,952 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:16:04,953 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:16:04,954 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:16:04,954 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:16:04,955 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:16:04,956 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:16:04,956 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:16:04,957 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:16:04,959 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:16:04,961 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:16:04,962 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:16:04,964 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:16:04,965 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:16:04,967 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:16:04,967 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:16:04,968 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:16:04,969 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:16:04,970 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:16:04,970 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:16:04,971 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:16:04,972 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:16:04,973 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:16:04,973 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:16:04,974 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:16:04,974 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:16:04,975 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:16:04,976 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:16:04,976 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 13:16:04,991 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:16:04,991 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:16:04,991 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:16:04,992 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:16:04,993 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:16:04,993 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:16:04,993 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:16:04,993 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:16:04,994 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:16:04,994 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:16:04,994 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:16:04,994 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:16:04,995 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:16:04,995 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:16:04,995 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:16:04,995 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:16:04,995 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:16:04,996 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:16:04,996 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:16:04,996 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:16:04,996 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:16:04,998 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:16:04,998 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:16:05,041 INFO ]: Repository-Root is: /tmp [2018-06-25 13:16:05,058 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:16:05,063 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:16:05,065 INFO ]: Initializing SmtParser... [2018-06-25 13:16:05,065 INFO ]: SmtParser initialized [2018-06-25 13:16:05,066 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested.c.smt2 [2018-06-25 13:16:05,067 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-25 13:16:05,167 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested.c.smt2 unknown [2018-06-25 13:16:05,422 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested.c.smt2 [2018-06-25 13:16:05,429 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:16:05,435 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:16:05,436 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:16:05,436 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:16:05,436 INFO ]: ChcToBoogie initialized [2018-06-25 13:16:05,440 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:16:05" (1/1) ... [2018-06-25 13:16:05,502 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05 Unit [2018-06-25 13:16:05,502 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:16:05,503 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:16:05,503 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:16:05,503 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:16:05,524 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (1/1) ... [2018-06-25 13:16:05,524 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (1/1) ... [2018-06-25 13:16:05,530 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (1/1) ... [2018-06-25 13:16:05,532 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (1/1) ... [2018-06-25 13:16:05,535 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (1/1) ... [2018-06-25 13:16:05,543 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (1/1) ... [2018-06-25 13:16:05,544 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (1/1) ... [2018-06-25 13:16:05,546 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:16:05,556 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:16:05,556 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:16:05,556 INFO ]: RCFGBuilder initialized [2018-06-25 13:16:05,557 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (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-25 13:16:05,573 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:16:05,573 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:16:05,573 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:16:05,574 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:16:05,574 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:16:05,574 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-25 13:16:05,849 INFO ]: Using library mode [2018-06-25 13:16:05,849 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:16:05 BoogieIcfgContainer [2018-06-25 13:16:05,850 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:16:05,860 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:16:05,860 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:16:05,863 INFO ]: TraceAbstraction initialized [2018-06-25 13:16:05,864 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:16:05" (1/3) ... [2018-06-25 13:16:05,864 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ae1bed8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:16:05, skipping insertion in model container [2018-06-25 13:16:05,865 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:16:05" (2/3) ... [2018-06-25 13:16:05,865 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ae1bed8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:16:05, skipping insertion in model container [2018-06-25 13:16:05,865 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:16:05" (3/3) ... [2018-06-25 13:16:05,867 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:16:05,885 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:16:05,907 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:16:05,950 INFO ]: Using default assertion order modulation [2018-06-25 13:16:05,951 INFO ]: Interprodecural is true [2018-06-25 13:16:05,951 INFO ]: Hoare is false [2018-06-25 13:16:05,951 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:16:05,951 INFO ]: Backedges is TWOTRACK [2018-06-25 13:16:05,951 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:16:05,951 INFO ]: Difference is false [2018-06-25 13:16:05,951 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:16:05,951 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:16:05,972 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:16:05,987 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:16:05,988 INFO ]: Found error trace [2018-06-25 13:16:05,990 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:05,990 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:05,995 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 13:16:05,997 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:05,999 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:06,053 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:06,053 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:16:06,053 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:06,091 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:06,150 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:06,152 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:16:06,152 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:16:06,154 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:16:06,167 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:16:06,167 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:16:06,169 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:16:06,214 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:16:06,214 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:16:06,214 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:16:06,215 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:16:06,216 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:16:06,224 INFO ]: With dead ends: 9 [2018-06-25 13:16:06,224 INFO ]: Without dead ends: 9 [2018-06-25 13:16:06,225 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:16:06,240 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:16:06,255 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:16:06,263 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:16:06,263 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:16:06,264 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:16:06,265 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:16:06,265 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:16:06,265 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:16:06,265 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:16:06,265 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:16:06,265 INFO ]: Found error trace [2018-06-25 13:16:06,265 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:06,265 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:06,265 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 13:16:06,265 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:06,265 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:06,267 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:06,267 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:16:06,267 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:06,307 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:06,436 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:06,437 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:16:06,437 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-25 13:16:06,452 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:16:06,511 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:06,523 INFO ]: Computing forward predicates... [2018-06-25 13:16:06,897 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:06,917 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:16:06,917 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 13:16:06,918 INFO ]: Interpolant automaton has 5 states [2018-06-25 13:16:06,918 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 13:16:06,918 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:16:06,918 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 13:16:07,040 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:16:07,041 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 13:16:07,041 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 13:16:07,041 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 13:16:07,042 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:16:07,042 INFO ]: With dead ends: 10 [2018-06-25 13:16:07,042 INFO ]: Without dead ends: 10 [2018-06-25 13:16:07,042 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:16:07,043 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 13:16:07,044 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 13:16:07,044 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 13:16:07,044 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 13:16:07,044 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 13:16:07,044 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:16:07,044 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 13:16:07,044 INFO ]: Interpolant automaton has 5 states. [2018-06-25 13:16:07,044 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 13:16:07,045 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 13:16:07,045 INFO ]: Found error trace [2018-06-25 13:16:07,045 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:07,045 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:07,047 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 13:16:07,047 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:07,047 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:07,048 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:07,048 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:16:07,048 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:07,081 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:07,392 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:07,392 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:16:07,392 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-25 13:16:07,399 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:16:07,465 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:16:07,465 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:07,468 INFO ]: Computing forward predicates... [2018-06-25 13:16:08,449 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:08,470 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:16:08,470 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 13:16:08,470 INFO ]: Interpolant automaton has 6 states [2018-06-25 13:16:08,470 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 13:16:08,470 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:16:08,471 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 13:16:08,569 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:16:08,569 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:16:08,570 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 13:16:08,570 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 13:16:08,570 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:16:08,570 INFO ]: With dead ends: 11 [2018-06-25 13:16:08,570 INFO ]: Without dead ends: 11 [2018-06-25 13:16:08,571 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-25 13:16:08,571 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:16:08,572 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:16:08,572 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:16:08,572 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:16:08,572 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 13:16:08,572 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:16:08,572 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:16:08,572 INFO ]: Interpolant automaton has 6 states. [2018-06-25 13:16:08,572 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:16:08,572 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:16:08,572 INFO ]: Found error trace [2018-06-25 13:16:08,573 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:08,573 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:08,573 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 13:16:08,573 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:08,573 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:08,574 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:08,574 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:16:08,574 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:08,631 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:09,082 WARN ]: Spent 291.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-25 13:16:09,158 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:09,158 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:16:09,158 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-25 13:16:09,164 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 13:16:09,225 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 13:16:09,225 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:09,228 INFO ]: Computing forward predicates... [2018-06-25 13:16:10,909 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:10,931 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:16:10,931 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-25 13:16:10,931 INFO ]: Interpolant automaton has 8 states [2018-06-25 13:16:10,932 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 13:16:10,932 INFO ]: CoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2018-06-25 13:16:10,932 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 8 states. [2018-06-25 13:16:11,075 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:16:11,075 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 13:16:11,075 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 13:16:11,075 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-25 13:16:11,076 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:16:11,076 INFO ]: With dead ends: 12 [2018-06-25 13:16:11,076 INFO ]: Without dead ends: 12 [2018-06-25 13:16:11,076 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=54, Invalid=78, Unknown=0, NotChecked=0, Total=132 [2018-06-25 13:16:11,076 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 13:16:11,078 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 13:16:11,078 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 13:16:11,078 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 13:16:11,078 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 13:16:11,078 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:16:11,078 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 13:16:11,078 INFO ]: Interpolant automaton has 8 states. [2018-06-25 13:16:11,078 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 13:16:11,079 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 13:16:11,079 INFO ]: Found error trace [2018-06-25 13:16:11,079 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:11,079 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:11,079 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 4 times [2018-06-25 13:16:11,079 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:11,079 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:11,080 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:11,080 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:16:11,080 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:11,115 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:11,278 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:11,279 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:16:11,279 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-25 13:16:11,284 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 13:16:11,310 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 13:16:11,310 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:11,312 INFO ]: Computing forward predicates... [2018-06-25 13:16:16,691 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:16,723 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:16:16,723 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-25 13:16:16,723 INFO ]: Interpolant automaton has 9 states [2018-06-25 13:16:16,723 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 13:16:16,723 INFO ]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-25 13:16:16,723 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 9 states. [2018-06-25 13:16:17,137 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:16:17,137 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 13:16:17,137 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 13:16:17,137 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-25 13:16:17,137 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:16:17,137 INFO ]: With dead ends: 13 [2018-06-25 13:16:17,137 INFO ]: Without dead ends: 13 [2018-06-25 13:16:17,138 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2018-06-25 13:16:17,138 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 13:16:17,139 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 13:16:17,139 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 13:16:17,139 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 13:16:17,139 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 13:16:17,139 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:16:17,139 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 13:16:17,139 INFO ]: Interpolant automaton has 9 states. [2018-06-25 13:16:17,139 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 13:16:17,141 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 13:16:17,141 INFO ]: Found error trace [2018-06-25 13:16:17,141 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:17,141 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:17,141 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 5 times [2018-06-25 13:16:17,141 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:17,141 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:17,142 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:17,142 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:16:17,142 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:17,252 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:17,743 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:17,743 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:16:17,743 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-25 13:16:17,751 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 13:16:17,806 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 13:16:17,807 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:17,810 INFO ]: Computing forward predicates... [2018-06-25 13:16:21,308 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:21,329 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:16:21,329 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-25 13:16:21,329 INFO ]: Interpolant automaton has 13 states [2018-06-25 13:16:21,329 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-25 13:16:21,329 INFO ]: CoverageRelationStatistics Valid=41, Invalid=115, Unknown=0, NotChecked=0, Total=156 [2018-06-25 13:16:21,330 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 13 states. [2018-06-25 13:16:21,643 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 13 [2018-06-25 13:16:21,766 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:16:21,766 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 13:16:21,963 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 13:16:21,963 INFO ]: Start accepts. Automaton has 13 states. Word has length 12 [2018-06-25 13:16:21,963 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:16:21,963 INFO ]: With dead ends: 14 [2018-06-25 13:16:21,963 INFO ]: Without dead ends: 14 [2018-06-25 13:16:21,964 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=115, Invalid=227, Unknown=0, NotChecked=0, Total=342 [2018-06-25 13:16:21,964 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 13:16:21,965 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 13:16:21,965 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 13:16:21,966 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 13:16:21,966 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-25 13:16:21,966 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:16:21,966 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 13:16:21,966 INFO ]: Interpolant automaton has 13 states. [2018-06-25 13:16:21,966 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 13:16:21,966 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 13:16:21,966 INFO ]: Found error trace [2018-06-25 13:16:21,966 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:21,966 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:21,967 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 6 times [2018-06-25 13:16:21,967 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:21,967 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:21,967 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:21,967 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:16:21,967 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:22,030 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:22,204 WARN ]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 13:16:22,371 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:22,371 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:16:22,371 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-25 13:16:22,390 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 13:16:22,429 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-25 13:16:22,429 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:22,433 INFO ]: Computing forward predicates... [2018-06-25 13:16:32,473 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:16:32,826 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:32,855 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:16:32,855 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-06-25 13:16:32,855 INFO ]: Interpolant automaton has 12 states [2018-06-25 13:16:32,855 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 13:16:32,855 INFO ]: CoverageRelationStatistics Valid=42, Invalid=90, Unknown=0, NotChecked=0, Total=132 [2018-06-25 13:16:32,855 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 12 states. [2018-06-25 13:16:33,303 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:16:33,303 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-25 13:16:33,303 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-25 13:16:33,303 INFO ]: Start accepts. Automaton has 12 states. Word has length 13 [2018-06-25 13:16:33,303 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:16:33,303 INFO ]: With dead ends: 16 [2018-06-25 13:16:33,303 INFO ]: Without dead ends: 16 [2018-06-25 13:16:33,304 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=146, Invalid=234, Unknown=0, NotChecked=0, Total=380 [2018-06-25 13:16:33,304 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-25 13:16:33,306 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-25 13:16:33,306 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-25 13:16:33,306 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-25 13:16:33,306 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 13 [2018-06-25 13:16:33,306 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:16:33,306 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-25 13:16:33,306 INFO ]: Interpolant automaton has 12 states. [2018-06-25 13:16:33,306 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-25 13:16:33,306 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-25 13:16:33,306 INFO ]: Found error trace [2018-06-25 13:16:33,307 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:33,307 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:33,307 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 7 times [2018-06-25 13:16:33,307 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:33,307 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:33,307 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:33,307 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:16:33,307 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:33,391 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:33,607 WARN ]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 13:16:34,663 WARN ]: Spent 1.00 s on a formula simplification. DAG size of input: 19 DAG size of output: 19 [2018-06-25 13:16:34,893 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 10 [2018-06-25 13:16:35,036 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:35,036 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:16:35,036 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-25 13:16:35,046 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:16:35,099 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:35,103 INFO ]: Computing forward predicates... [2018-06-25 13:16:36,863 WARN ]: Spent 183.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 18 [2018-06-25 13:16:37,046 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:37,068 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:16:37,068 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 19 [2018-06-25 13:16:37,069 INFO ]: Interpolant automaton has 19 states [2018-06-25 13:16:37,069 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-25 13:16:37,069 INFO ]: CoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2018-06-25 13:16:37,069 INFO ]: Start difference. First operand 16 states and 16 transitions. Second operand 19 states. [2018-06-25 13:16:37,398 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 27 [2018-06-25 13:16:37,596 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 23 [2018-06-25 13:16:37,882 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 24 [2018-06-25 13:16:37,883 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:16:37,883 INFO ]: Finished difference Result 17 states and 17 transitions. [2018-06-25 13:16:37,883 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-25 13:16:37,883 INFO ]: Start accepts. Automaton has 19 states. Word has length 15 [2018-06-25 13:16:37,884 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:16:37,884 INFO ]: With dead ends: 17 [2018-06-25 13:16:37,884 INFO ]: Without dead ends: 17 [2018-06-25 13:16:37,885 INFO ]: 0 DeclaredPredicates, 33 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=207, Invalid=495, Unknown=0, NotChecked=0, Total=702 [2018-06-25 13:16:37,885 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-25 13:16:37,886 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-25 13:16:37,886 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-25 13:16:37,886 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-06-25 13:16:37,886 INFO ]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 15 [2018-06-25 13:16:37,887 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:16:37,887 INFO ]: Abstraction has 17 states and 17 transitions. [2018-06-25 13:16:37,887 INFO ]: Interpolant automaton has 19 states. [2018-06-25 13:16:37,887 INFO ]: Start isEmpty. Operand 17 states and 17 transitions. [2018-06-25 13:16:37,887 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-25 13:16:37,887 INFO ]: Found error trace [2018-06-25 13:16:37,887 INFO ]: trace histogram [9, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:16:37,887 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:16:37,887 INFO ]: Analyzing trace with hash -1752374252, now seen corresponding path program 8 times [2018-06-25 13:16:37,887 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:16:37,887 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:16:37,888 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:37,888 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:16:37,888 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:16:37,975 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:38,396 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:16:38,396 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:16:38,396 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-25 13:16:38,402 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:16:38,450 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:16:38,450 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:16:38,453 INFO ]: Computing forward predicates... [2018-06-25 13:16:41,463 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:16:41,471 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 13:17:12,368 INFO ]: Timeout while computing interpolants [2018-06-25 13:17:12,599 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:17:12,599 WARN ]: Verification canceled [2018-06-25 13:17:12,604 WARN ]: Timeout [2018-06-25 13:17:12,604 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:17:12 BoogieIcfgContainer [2018-06-25 13:17:12,604 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:17:12,605 INFO ]: Toolchain (without parser) took 67175.64 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 263.2 MB in the beginning and 1.4 GB in the end (delta: -1.2 GB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:17:12,606 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:17:12,606 INFO ]: ChcToBoogie took 66.26 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:17:12,606 INFO ]: Boogie Preprocessor took 43.69 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 259.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:17:12,607 INFO ]: RCFGBuilder took 293.67 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 249.2 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:17:12,607 INFO ]: TraceAbstraction took 66743.72 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 249.2 MB in the beginning and 1.4 GB in the end (delta: -1.2 GB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:17:12,611 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 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 66.26 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.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.69 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 259.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 293.67 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 249.2 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 66743.72 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 249.2 MB in the beginning and 1.4 GB in the end (delta: -1.2 GB). Peak memory consumption was 1.3 GB. 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 17 with TraceHistMax 9, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 20996 quantified variables from 12 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 66.6s OverallTime, 9 OverallIterations, 9 TraceHistogramMax, 2.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 30 SDslu, 190 SDs, 0 SdLazy, 77 SolverSat, 67 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 158 GetRequests, 52 SyntacticMatches, 13 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 251 ImplicationChecksByTransitivity, 6.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=17occurred in iteration=8, 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, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 27.9s InterpolantComputationTime, 163 NumberOfCodeBlocks, 163 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 148 ConstructedInterpolants, 0 QuantifiedInterpolants, 9759 SizeOfPredicates, 28 NumberOfNonLiveVariables, 1113 ConjunctsInSsa, 256 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/184 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/nested.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-17-12-626.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nested.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-17-12-626.csv Completed graceful shutdown