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/nested8.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:14:56,929 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:14:56,931 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:14:56,943 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:14:56,943 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:14:56,944 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:14:56,945 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:14:56,948 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:14:56,949 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:14:56,950 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:14:56,950 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:14:56,951 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:14:56,951 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:14:56,952 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:14:56,955 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:14:56,956 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:14:56,957 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:14:56,969 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:14:56,973 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:14:56,974 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:14:56,975 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:14:56,980 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:14:56,981 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:14:56,981 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:14:56,982 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:14:56,983 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:14:56,983 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:14:56,984 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:14:56,985 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:14:56,985 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:14:56,986 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:14:56,986 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:14:56,986 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:14:56,987 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:14:56,988 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:14:56,988 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:14:57,007 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:14:57,007 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:14:57,008 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:14:57,008 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:14:57,009 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:14:57,009 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:14:57,009 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:14:57,010 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:14:57,010 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:14:57,010 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:14:57,010 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:14:57,010 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:14:57,011 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:14:57,011 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:14:57,011 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:14:57,011 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:14:57,012 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:14:57,012 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:14:57,012 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:14:57,012 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:14:57,012 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:14:57,014 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:14:57,014 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:14:57,066 INFO ]: Repository-Root is: /tmp [2018-06-25 13:14:57,084 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:14:57,090 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:14:57,091 INFO ]: Initializing SmtParser... [2018-06-25 13:14:57,092 INFO ]: SmtParser initialized [2018-06-25 13:14:57,092 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested8.c.smt2 [2018-06-25 13:14:57,093 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:14:57,168 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested8.c.smt2 unknown [2018-06-25 13:14:57,449 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested8.c.smt2 [2018-06-25 13:14:57,454 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:14:57,461 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:14:57,462 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:14:57,462 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:14:57,462 INFO ]: ChcToBoogie initialized [2018-06-25 13:14:57,465 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:14:57" (1/1) ... [2018-06-25 13:14:57,523 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57 Unit [2018-06-25 13:14:57,523 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:14:57,524 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:14:57,524 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:14:57,524 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:14:57,545 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (1/1) ... [2018-06-25 13:14:57,545 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (1/1) ... [2018-06-25 13:14:57,552 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (1/1) ... [2018-06-25 13:14:57,552 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (1/1) ... [2018-06-25 13:14:57,565 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (1/1) ... [2018-06-25 13:14:57,567 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (1/1) ... [2018-06-25 13:14:57,568 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (1/1) ... [2018-06-25 13:14:57,575 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:14:57,575 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:14:57,575 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:14:57,575 INFO ]: RCFGBuilder initialized [2018-06-25 13:14:57,576 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (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:14:57,599 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:14:57,599 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:14:57,599 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:14:57,599 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:14:57,599 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:14:57,599 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:14:57,877 INFO ]: Using library mode [2018-06-25 13:14:57,878 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:14:57 BoogieIcfgContainer [2018-06-25 13:14:57,878 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:14:57,886 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:14:57,886 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:14:57,890 INFO ]: TraceAbstraction initialized [2018-06-25 13:14:57,890 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:14:57" (1/3) ... [2018-06-25 13:14:57,891 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@60d32dd0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:14:57, skipping insertion in model container [2018-06-25 13:14:57,891 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:14:57" (2/3) ... [2018-06-25 13:14:57,891 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@60d32dd0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:14:57, skipping insertion in model container [2018-06-25 13:14:57,891 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:14:57" (3/3) ... [2018-06-25 13:14:57,893 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:14:57,902 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:14:57,910 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:14:57,954 INFO ]: Using default assertion order modulation [2018-06-25 13:14:57,955 INFO ]: Interprodecural is true [2018-06-25 13:14:57,955 INFO ]: Hoare is false [2018-06-25 13:14:57,955 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:14:57,955 INFO ]: Backedges is TWOTRACK [2018-06-25 13:14:57,955 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:14:57,955 INFO ]: Difference is false [2018-06-25 13:14:57,955 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:14:57,955 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:14:57,970 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:14:57,988 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:14:57,988 INFO ]: Found error trace [2018-06-25 13:14:57,989 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:14:57,989 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:14:57,998 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 13:14:58,000 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:14:58,001 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:14:58,037 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:14:58,037 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:14:58,037 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:14:58,077 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:14:58,169 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:14:58,170 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:14:58,170 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:14:58,172 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:14:58,182 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:14:58,183 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:14:58,185 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:14:58,256 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:14:58,256 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:14:58,257 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:14:58,258 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:14:58,258 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:14:58,271 INFO ]: With dead ends: 9 [2018-06-25 13:14:58,271 INFO ]: Without dead ends: 9 [2018-06-25 13:14:58,273 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:14:58,285 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:14:58,305 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:14:58,315 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:14:58,315 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:14:58,317 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:14:58,317 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:14:58,317 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:14:58,317 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:14:58,317 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:14:58,317 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:14:58,317 INFO ]: Found error trace [2018-06-25 13:14:58,317 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:14:58,318 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:14:58,318 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 13:14:58,318 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:14:58,318 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:14:58,319 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:14:58,319 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:14:58,319 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:14:58,354 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:14:58,489 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:14:58,489 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:14:58,489 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-25 13:14:58,495 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:14:58,547 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:14:58,557 INFO ]: Computing forward predicates... [2018-06-25 13:14:59,362 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:14:59,389 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:14:59,389 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 13:14:59,389 INFO ]: Interpolant automaton has 5 states [2018-06-25 13:14:59,389 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 13:14:59,389 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:14:59,390 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 13:14:59,524 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:14:59,524 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 13:14:59,527 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 13:14:59,527 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 13:14:59,527 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:14:59,528 INFO ]: With dead ends: 10 [2018-06-25 13:14:59,528 INFO ]: Without dead ends: 10 [2018-06-25 13:14:59,529 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:14:59,529 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 13:14:59,530 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 13:14:59,530 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 13:14:59,530 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 13:14:59,530 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 13:14:59,530 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:14:59,530 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 13:14:59,530 INFO ]: Interpolant automaton has 5 states. [2018-06-25 13:14:59,530 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 13:14:59,531 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 13:14:59,531 INFO ]: Found error trace [2018-06-25 13:14:59,531 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:14:59,531 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:14:59,531 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 13:14:59,531 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:14:59,531 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:14:59,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:14:59,532 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:14:59,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:14:59,614 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:14:59,904 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 7 [2018-06-25 13:14:59,951 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:14:59,951 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:14:59,951 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:14:59,958 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:15:00,011 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:15:00,011 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:00,014 INFO ]: Computing forward predicates... [2018-06-25 13:15:02,102 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:15:02,122 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:15:02,122 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 13:15:02,122 INFO ]: Interpolant automaton has 6 states [2018-06-25 13:15:02,123 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 13:15:02,123 INFO ]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:15:02,123 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 13:15:02,339 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:15:02,340 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:15:02,340 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 13:15:02,340 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 13:15:02,340 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:15:02,340 INFO ]: With dead ends: 11 [2018-06-25 13:15:02,340 INFO ]: Without dead ends: 11 [2018-06-25 13:15:02,341 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2018-06-25 13:15:02,341 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:15:02,342 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:15:02,342 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:15:02,342 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:15:02,342 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 13:15:02,342 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:15:02,342 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:15:02,342 INFO ]: Interpolant automaton has 6 states. [2018-06-25 13:15:02,342 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:15:02,343 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:15:02,343 INFO ]: Found error trace [2018-06-25 13:15:02,343 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:15:02,343 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:15:02,343 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 13:15:02,343 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:15:02,343 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:15:02,344 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:02,344 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:15:02,344 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:02,386 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:02,601 WARN ]: Spent 142.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 8 [2018-06-25 13:15:02,642 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:15:02,642 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:15:02,642 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:15:02,673 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 13:15:02,710 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 13:15:02,710 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:02,714 INFO ]: Computing forward predicates... [2018-06-25 13:15:08,363 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:15:08,399 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:15:08,399 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-25 13:15:08,399 INFO ]: Interpolant automaton has 8 states [2018-06-25 13:15:08,399 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 13:15:08,399 INFO ]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2018-06-25 13:15:08,399 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 8 states. [2018-06-25 13:15:08,594 WARN ]: Spent 128.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 13:15:08,722 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:15:08,722 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 13:15:08,722 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 13:15:08,722 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-25 13:15:08,722 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:15:08,722 INFO ]: With dead ends: 12 [2018-06-25 13:15:08,722 INFO ]: Without dead ends: 12 [2018-06-25 13:15:08,723 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=56, Invalid=76, Unknown=0, NotChecked=0, Total=132 [2018-06-25 13:15:08,723 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 13:15:08,724 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 13:15:08,724 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 13:15:08,724 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 13:15:08,724 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 13:15:08,725 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:15:08,725 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 13:15:08,725 INFO ]: Interpolant automaton has 8 states. [2018-06-25 13:15:08,725 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 13:15:08,725 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 13:15:08,725 INFO ]: Found error trace [2018-06-25 13:15:08,725 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:15:08,725 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:15:08,725 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 4 times [2018-06-25 13:15:08,725 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:15:08,725 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:15:08,726 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:08,726 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:15:08,726 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:08,785 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:09,002 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:15:09,002 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:15:09,002 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:15:09,009 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 13:15:09,047 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 13:15:09,047 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:09,051 INFO ]: Computing forward predicates... [2018-06-25 13:15:11,453 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 12 [2018-06-25 13:15:14,670 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:15:14,727 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:15:14,727 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-25 13:15:14,728 INFO ]: Interpolant automaton has 9 states [2018-06-25 13:15:14,728 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 13:15:14,728 INFO ]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-25 13:15:14,728 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 9 states. [2018-06-25 13:15:14,864 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:15:14,864 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 13:15:14,864 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 13:15:14,864 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-25 13:15:14,864 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:15:14,865 INFO ]: With dead ends: 13 [2018-06-25 13:15:14,865 INFO ]: Without dead ends: 13 [2018-06-25 13:15:14,865 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2018-06-25 13:15:14,865 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 13:15:14,866 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 13:15:14,867 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 13:15:14,867 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 13:15:14,867 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 13:15:14,867 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:15:14,867 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 13:15:14,867 INFO ]: Interpolant automaton has 9 states. [2018-06-25 13:15:14,867 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 13:15:14,867 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 13:15:14,867 INFO ]: Found error trace [2018-06-25 13:15:14,867 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:15:14,868 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:15:14,868 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 5 times [2018-06-25 13:15:14,868 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:15:14,868 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:15:14,868 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:14,868 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:15:14,868 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:14,954 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:15,235 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:15:15,235 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:15:15,235 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:15:15,244 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 13:15:15,285 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 13:15:15,285 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:15,289 INFO ]: Computing forward predicates... [2018-06-25 13:15:42,336 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:15:42,356 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:15:42,356 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2018-06-25 13:15:42,356 INFO ]: Interpolant automaton has 9 states [2018-06-25 13:15:42,356 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 13:15:42,356 INFO ]: CoverageRelationStatistics Valid=23, Invalid=49, Unknown=0, NotChecked=0, Total=72 [2018-06-25 13:15:42,356 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 9 states. [2018-06-25 13:15:42,528 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:15:42,528 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 13:15:42,528 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 13:15:42,528 INFO ]: Start accepts. Automaton has 9 states. Word has length 12 [2018-06-25 13:15:42,528 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:15:42,529 INFO ]: With dead ends: 14 [2018-06-25 13:15:42,529 INFO ]: Without dead ends: 14 [2018-06-25 13:15:42,529 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=134, Unknown=0, NotChecked=0, Total=210 [2018-06-25 13:15:42,529 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 13:15:42,530 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 13:15:42,530 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 13:15:42,530 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 13:15:42,530 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-25 13:15:42,530 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:15:42,530 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 13:15:42,530 INFO ]: Interpolant automaton has 9 states. [2018-06-25 13:15:42,530 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 13:15:42,531 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 13:15:42,531 INFO ]: Found error trace [2018-06-25 13:15:42,531 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:15:42,531 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:15:42,531 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 6 times [2018-06-25 13:15:42,531 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:15:42,531 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:15:42,531 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:42,531 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:15:42,531 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:42,608 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:43,022 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:15:43,022 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:15:43,022 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:15:43,028 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 13:15:43,078 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-25 13:15:43,078 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:43,082 INFO ]: Computing forward predicates... [2018-06-25 13:15:46,634 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 10 [2018-06-25 13:15:46,844 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:15:48,873 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 13:15:48,876 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:15:48,879 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:15:50,884 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:15:50,917 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:15:50,917 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-06-25 13:15:50,917 INFO ]: Interpolant automaton has 12 states [2018-06-25 13:15:50,918 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 13:15:50,918 INFO ]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2018-06-25 13:15:50,918 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 12 states. [2018-06-25 13:15:51,151 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:15:51,151 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-25 13:15:51,151 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-25 13:15:51,151 INFO ]: Start accepts. Automaton has 12 states. Word has length 13 [2018-06-25 13:15:51,151 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:15:51,152 INFO ]: With dead ends: 15 [2018-06-25 13:15:51,152 INFO ]: Without dead ends: 15 [2018-06-25 13:15:51,152 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=100, Invalid=242, Unknown=0, NotChecked=0, Total=342 [2018-06-25 13:15:51,152 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-25 13:15:51,153 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-25 13:15:51,153 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-25 13:15:51,154 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-25 13:15:51,154 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-25 13:15:51,154 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:15:51,154 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-25 13:15:51,154 INFO ]: Interpolant automaton has 12 states. [2018-06-25 13:15:51,154 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-25 13:15:51,154 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-25 13:15:51,154 INFO ]: Found error trace [2018-06-25 13:15:51,154 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:15:51,154 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:15:51,155 INFO ]: Analyzing trace with hash 726730004, now seen corresponding path program 7 times [2018-06-25 13:15:51,155 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:15:51,155 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:15:51,155 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:51,155 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:15:51,155 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:15:51,224 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:51,614 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:15:51,614 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:15:51,614 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:15:51,623 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:15:51,673 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:15:51,677 INFO ]: Computing forward predicates... [2018-06-25 13:16:00,848 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 13:16:01,662 INFO ]: Timeout while computing interpolants [2018-06-25 13:16:01,862 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:16:01,862 WARN ]: Verification canceled [2018-06-25 13:16:01,866 WARN ]: Timeout [2018-06-25 13:16:01,866 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:16:01 BoogieIcfgContainer [2018-06-25 13:16:01,866 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:16:01,867 INFO ]: Toolchain (without parser) took 64413.00 ms. Allocated memory was 296.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 249.1 MB in the beginning and 156.0 MB in the end (delta: 93.1 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:16:01,868 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 296.7 MB. Free memory is still 262.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:16:01,868 INFO ]: ChcToBoogie took 61.28 ms. Allocated memory is still 296.7 MB. Free memory was 249.1 MB in the beginning and 246.1 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:16:01,869 INFO ]: Boogie Preprocessor took 50.71 ms. Allocated memory is still 296.7 MB. Free memory was 246.1 MB in the beginning and 245.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-25 13:16:01,869 INFO ]: RCFGBuilder took 302.78 ms. Allocated memory is still 296.7 MB. Free memory was 245.1 MB in the beginning and 234.2 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:16:01,870 INFO ]: TraceAbstraction took 63980.21 ms. Allocated memory was 296.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 234.2 MB in the beginning and 156.0 MB in the end (delta: 78.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:16:01,872 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 296.7 MB. Free memory is still 262.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 61.28 ms. Allocated memory is still 296.7 MB. Free memory was 249.1 MB in the beginning and 246.1 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 50.71 ms. Allocated memory is still 296.7 MB. Free memory was 246.1 MB in the beginning and 245.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 302.78 ms. Allocated memory is still 296.7 MB. Free memory was 245.1 MB in the beginning and 234.2 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63980.21 ms. Allocated memory was 296.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 234.2 MB in the beginning and 156.0 MB in the end (delta: 78.2 MB). 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 15 with TraceHistMax 7, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was transforming 0 conjuction. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 63.9s OverallTime, 8 OverallIterations, 7 TraceHistogramMax, 1.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 49 SDtfs, 19 SDslu, 126 SDs, 0 SdLazy, 54 SolverSat, 41 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 125 GetRequests, 44 SyntacticMatches, 17 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 3.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=15occurred in iteration=7, 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, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 50.7s InterpolantComputationTime, 133 NumberOfCodeBlocks, 133 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 120 ConstructedInterpolants, 0 QuantifiedInterpolants, 5351 SizeOfPredicates, 30 NumberOfNonLiveVariables, 1125 ConjunctsInSsa, 216 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 0/112 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/nested8.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-16-01-884.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nested8.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-16-01-884.csv Completed graceful shutdown