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/dillig32.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:56:30,279 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:56:30,281 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:56:30,294 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:56:30,294 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:56:30,295 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:56:30,298 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:56:30,300 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:56:30,302 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:56:30,302 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:56:30,304 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:56:30,305 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:56:30,306 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:56:30,307 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:56:30,307 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:56:30,310 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:56:30,312 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:56:30,321 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:56:30,322 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:56:30,323 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:56:30,324 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:56:30,329 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:56:30,330 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:56:30,330 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:56:30,331 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:56:30,335 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:56:30,335 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:56:30,336 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:56:30,341 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:56:30,342 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:56:30,342 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:56:30,343 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:56:30,343 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:56:30,344 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:56:30,344 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:56:30,346 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 12:56:30,364 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:56:30,364 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:56:30,365 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:56:30,365 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:56:30,366 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:56:30,366 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:56:30,366 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:56:30,366 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:56:30,368 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:56:30,368 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:56:30,368 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:56:30,368 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:56:30,368 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:56:30,369 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:56:30,369 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:56:30,369 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:56:30,369 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:56:30,369 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:56:30,369 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:56:30,370 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:56:30,371 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:56:30,373 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:56:30,373 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:56:30,427 INFO ]: Repository-Root is: /tmp [2018-06-25 12:56:30,444 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:56:30,449 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:56:30,451 INFO ]: Initializing SmtParser... [2018-06-25 12:56:30,451 INFO ]: SmtParser initialized [2018-06-25 12:56:30,452 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig32.c.smt2 [2018-06-25 12:56:30,453 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 12:56:30,536 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig32.c.smt2 unknown [2018-06-25 12:56:30,996 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig32.c.smt2 [2018-06-25 12:56:31,002 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:56:31,008 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:56:31,009 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:56:31,009 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:56:31,009 INFO ]: ChcToBoogie initialized [2018-06-25 12:56:31,012 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:56:30" (1/1) ... [2018-06-25 12:56:31,071 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31 Unit [2018-06-25 12:56:31,071 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:56:31,072 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:56:31,072 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:56:31,072 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:56:31,094 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (1/1) ... [2018-06-25 12:56:31,094 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (1/1) ... [2018-06-25 12:56:31,102 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (1/1) ... [2018-06-25 12:56:31,102 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (1/1) ... [2018-06-25 12:56:31,117 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (1/1) ... [2018-06-25 12:56:31,119 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (1/1) ... [2018-06-25 12:56:31,121 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (1/1) ... [2018-06-25 12:56:31,123 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:56:31,128 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:56:31,128 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:56:31,128 INFO ]: RCFGBuilder initialized [2018-06-25 12:56:31,129 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (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 12:56:31,155 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:56:31,156 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:56:31,156 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:56:31,156 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:56:31,156 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:56:31,156 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 12:56:31,397 INFO ]: Using library mode [2018-06-25 12:56:31,398 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:56:31 BoogieIcfgContainer [2018-06-25 12:56:31,398 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:56:31,401 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:56:31,401 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:56:31,404 INFO ]: TraceAbstraction initialized [2018-06-25 12:56:31,404 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:56:30" (1/3) ... [2018-06-25 12:56:31,405 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@85af601 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:56:31, skipping insertion in model container [2018-06-25 12:56:31,405 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:56:31" (2/3) ... [2018-06-25 12:56:31,405 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@85af601 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:56:31, skipping insertion in model container [2018-06-25 12:56:31,405 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:56:31" (3/3) ... [2018-06-25 12:56:31,407 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:56:31,416 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:56:31,425 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:56:31,475 INFO ]: Using default assertion order modulation [2018-06-25 12:56:31,476 INFO ]: Interprodecural is true [2018-06-25 12:56:31,476 INFO ]: Hoare is false [2018-06-25 12:56:31,476 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:56:31,476 INFO ]: Backedges is TWOTRACK [2018-06-25 12:56:31,476 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:56:31,476 INFO ]: Difference is false [2018-06-25 12:56:31,476 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:56:31,476 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:56:31,495 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:56:31,508 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:56:31,508 INFO ]: Found error trace [2018-06-25 12:56:31,509 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:56:31,509 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:56:31,517 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 12:56:31,519 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:56:31,520 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:56:31,554 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:31,554 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:56:31,554 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:31,594 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:31,667 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:31,673 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:56:31,674 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:56:31,676 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:56:31,690 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:56:31,692 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:56:31,694 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:56:31,795 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:56:31,795 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:56:31,799 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:56:31,800 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:56:31,800 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:56:31,811 INFO ]: With dead ends: 9 [2018-06-25 12:56:31,811 INFO ]: Without dead ends: 9 [2018-06-25 12:56:31,813 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 12:56:31,831 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:56:31,860 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:56:31,861 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:56:31,865 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:56:31,867 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:56:31,867 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:56:31,867 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:56:31,867 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:56:31,867 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:56:31,867 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:56:31,867 INFO ]: Found error trace [2018-06-25 12:56:31,867 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:56:31,867 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:56:31,868 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 12:56:31,868 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:56:31,868 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:56:31,869 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:31,869 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:56:31,869 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:31,922 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:32,078 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:32,078 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:56:32,078 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 12:56:32,086 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:56:32,125 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:32,135 INFO ]: Computing forward predicates... [2018-06-25 12:56:32,379 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:32,413 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:56:32,413 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 12:56:32,413 INFO ]: Interpolant automaton has 5 states [2018-06-25 12:56:32,413 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 12:56:32,414 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 12:56:32,414 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 12:56:32,553 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:56:32,553 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 12:56:32,554 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 12:56:32,554 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 12:56:32,554 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:56:32,554 INFO ]: With dead ends: 10 [2018-06-25 12:56:32,554 INFO ]: Without dead ends: 10 [2018-06-25 12:56:32,555 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:56:32,555 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 12:56:32,556 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 12:56:32,556 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 12:56:32,556 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 12:56:32,556 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 12:56:32,557 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:56:32,557 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 12:56:32,557 INFO ]: Interpolant automaton has 5 states. [2018-06-25 12:56:32,557 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 12:56:32,558 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 12:56:32,558 INFO ]: Found error trace [2018-06-25 12:56:32,558 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:56:32,558 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:56:32,559 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 12:56:32,559 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:56:32,559 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:56:32,560 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:32,560 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:56:32,560 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:32,627 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:32,819 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:32,819 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:56:32,819 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 12:56:32,825 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:56:32,869 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:56:32,869 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:32,872 INFO ]: Computing forward predicates... [2018-06-25 12:56:33,848 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:33,869 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:56:33,869 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 12:56:33,869 INFO ]: Interpolant automaton has 6 states [2018-06-25 12:56:33,869 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 12:56:33,869 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:56:33,869 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 12:56:34,016 WARN ]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-25 12:56:34,023 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:56:34,023 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 12:56:34,024 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 12:56:34,024 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 12:56:34,024 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:56:34,024 INFO ]: With dead ends: 11 [2018-06-25 12:56:34,024 INFO ]: Without dead ends: 11 [2018-06-25 12:56:34,025 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=26, Invalid=30, Unknown=0, NotChecked=0, Total=56 [2018-06-25 12:56:34,025 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 12:56:34,026 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 12:56:34,026 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 12:56:34,026 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 12:56:34,026 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 12:56:34,026 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:56:34,026 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 12:56:34,027 INFO ]: Interpolant automaton has 6 states. [2018-06-25 12:56:34,027 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 12:56:34,027 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 12:56:34,027 INFO ]: Found error trace [2018-06-25 12:56:34,027 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:56:34,027 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:56:34,027 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 12:56:34,027 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:56:34,027 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:56:34,028 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:34,028 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:56:34,028 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:34,057 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:34,226 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:34,226 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:56:34,226 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 12:56:34,233 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:56:34,289 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:56:34,289 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:34,292 INFO ]: Computing forward predicates... [2018-06-25 12:56:35,915 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:35,946 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:56:35,946 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 12:56:35,946 INFO ]: Interpolant automaton has 7 states [2018-06-25 12:56:35,946 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 12:56:35,946 INFO ]: CoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2018-06-25 12:56:35,947 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-25 12:56:36,137 WARN ]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 12:56:37,023 WARN ]: Spent 788.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 10 [2018-06-25 12:56:38,117 WARN ]: Spent 173.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-25 12:56:38,392 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 9 [2018-06-25 12:56:38,393 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:56:38,393 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:56:38,393 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 12:56:38,394 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-25 12:56:38,394 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:56:38,394 INFO ]: With dead ends: 12 [2018-06-25 12:56:38,394 INFO ]: Without dead ends: 12 [2018-06-25 12:56:38,394 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=42, Invalid=68, Unknown=0, NotChecked=0, Total=110 [2018-06-25 12:56:38,395 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:56:38,396 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:56:38,396 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:56:38,397 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:56:38,397 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 12:56:38,397 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:56:38,397 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:56:38,397 INFO ]: Interpolant automaton has 7 states. [2018-06-25 12:56:38,397 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:56:38,397 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:56:38,397 INFO ]: Found error trace [2018-06-25 12:56:38,397 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:56:38,397 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:56:38,397 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 4 times [2018-06-25 12:56:38,397 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:56:38,397 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:56:38,398 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:38,398 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:56:38,398 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:38,459 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:38,654 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:38,654 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:56:38,654 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 12:56:38,662 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 12:56:38,713 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 12:56:38,713 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:38,717 INFO ]: Computing forward predicates... [2018-06-25 12:56:39,706 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:56:41,309 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:41,329 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:56:41,329 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-25 12:56:41,329 INFO ]: Interpolant automaton has 9 states [2018-06-25 12:56:41,330 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 12:56:41,330 INFO ]: CoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-25 12:56:41,330 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 9 states. [2018-06-25 12:56:41,578 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:56:41,578 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 12:56:41,578 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 12:56:41,578 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-25 12:56:41,579 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:56:41,579 INFO ]: With dead ends: 13 [2018-06-25 12:56:41,579 INFO ]: Without dead ends: 13 [2018-06-25 12:56:41,579 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2018-06-25 12:56:41,579 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 12:56:41,581 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 12:56:41,581 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 12:56:41,581 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 12:56:41,581 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 12:56:41,581 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:56:41,581 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 12:56:41,581 INFO ]: Interpolant automaton has 9 states. [2018-06-25 12:56:41,581 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 12:56:41,582 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 12:56:41,582 INFO ]: Found error trace [2018-06-25 12:56:41,582 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:56:41,582 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:56:41,582 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 5 times [2018-06-25 12:56:41,582 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:56:41,582 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:56:41,583 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:41,583 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:56:41,583 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:41,622 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:41,813 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:41,813 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:56:41,813 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 12:56:41,825 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 12:56:41,866 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 12:56:41,866 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:41,870 INFO ]: Computing forward predicates... [2018-06-25 12:56:43,125 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:56:43,155 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 12:56:48,250 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:49,204 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:56:49,206 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-25 12:56:49,206 INFO ]: Interpolant automaton has 11 states [2018-06-25 12:56:49,206 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-25 12:56:49,206 INFO ]: CoverageRelationStatistics Valid=38, Invalid=72, Unknown=0, NotChecked=0, Total=110 [2018-06-25 12:56:49,206 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 11 states. [2018-06-25 12:56:49,550 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:56:49,550 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 12:56:49,551 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 12:56:49,551 INFO ]: Start accepts. Automaton has 11 states. Word has length 12 [2018-06-25 12:56:49,551 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:56:49,551 INFO ]: With dead ends: 14 [2018-06-25 12:56:49,551 INFO ]: Without dead ends: 14 [2018-06-25 12:56:49,552 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=106, Invalid=166, Unknown=0, NotChecked=0, Total=272 [2018-06-25 12:56:49,552 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 12:56:49,553 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 12:56:49,553 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 12:56:49,553 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 12:56:49,553 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-25 12:56:49,553 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:56:49,553 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 12:56:49,553 INFO ]: Interpolant automaton has 11 states. [2018-06-25 12:56:49,553 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 12:56:49,554 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 12:56:49,554 INFO ]: Found error trace [2018-06-25 12:56:49,554 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:56:49,554 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:56:49,554 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 6 times [2018-06-25 12:56:49,554 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:56:49,554 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:56:49,555 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:49,555 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:56:49,555 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:56:49,646 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:50,338 WARN ]: Spent 454.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-25 12:56:50,802 WARN ]: Spent 386.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-25 12:56:50,930 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:56:50,930 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:56:50,930 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 12:56:50,939 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 12:56:50,988 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-25 12:56:50,988 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:56:50,992 INFO ]: Computing forward predicates... [2018-06-25 12:56:51,980 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:57:03,928 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:57:03,950 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:57:03,950 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 11 [2018-06-25 12:57:03,950 INFO ]: Interpolant automaton has 11 states [2018-06-25 12:57:03,950 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-25 12:57:03,951 INFO ]: CoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-06-25 12:57:03,951 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 11 states. [2018-06-25 12:57:04,358 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:57:04,358 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-25 12:57:04,358 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-25 12:57:04,358 INFO ]: Start accepts. Automaton has 11 states. Word has length 13 [2018-06-25 12:57:04,358 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:57:04,359 INFO ]: With dead ends: 15 [2018-06-25 12:57:04,359 INFO ]: Without dead ends: 15 [2018-06-25 12:57:04,359 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 5 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=117, Invalid=189, Unknown=0, NotChecked=0, Total=306 [2018-06-25 12:57:04,359 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-25 12:57:04,360 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-25 12:57:04,361 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-25 12:57:04,361 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-25 12:57:04,361 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-25 12:57:04,361 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:57:04,361 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-25 12:57:04,361 INFO ]: Interpolant automaton has 11 states. [2018-06-25 12:57:04,361 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-25 12:57:04,361 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-25 12:57:04,361 INFO ]: Found error trace [2018-06-25 12:57:04,361 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:57:04,362 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:57:04,362 INFO ]: Analyzing trace with hash 726730004, now seen corresponding path program 7 times [2018-06-25 12:57:04,362 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:57:04,362 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:57:04,363 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:57:04,363 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:57:04,363 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:57:04,425 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:57:04,983 WARN ]: Spent 372.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-25 12:57:05,069 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:57:05,070 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:57:05,070 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) [2018-06-25 12:57:05,086 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:57:05,141 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:57:05,145 INFO ]: Computing forward predicates... [2018-06-25 12:57:05,845 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:57:12,150 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:57:12,181 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:57:12,181 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 12 [2018-06-25 12:57:12,182 INFO ]: Interpolant automaton has 12 states [2018-06-25 12:57:12,182 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 12:57:12,182 INFO ]: CoverageRelationStatistics Valid=33, Invalid=99, Unknown=0, NotChecked=0, Total=132 [2018-06-25 12:57:12,182 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 12 states. [2018-06-25 12:57:12,625 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:57:12,625 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-25 12:57:12,625 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-25 12:57:12,625 INFO ]: Start accepts. Automaton has 12 states. Word has length 14 [2018-06-25 12:57:12,625 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:57:12,625 INFO ]: With dead ends: 16 [2018-06-25 12:57:12,625 INFO ]: Without dead ends: 16 [2018-06-25 12:57:12,626 INFO ]: 0 DeclaredPredicates, 31 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=127, Invalid=253, Unknown=0, NotChecked=0, Total=380 [2018-06-25 12:57:12,626 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-25 12:57:12,627 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-25 12:57:12,627 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-25 12:57:12,628 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-25 12:57:12,628 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-06-25 12:57:12,628 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:57:12,628 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-25 12:57:12,628 INFO ]: Interpolant automaton has 12 states. [2018-06-25 12:57:12,628 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-25 12:57:12,628 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-25 12:57:12,629 INFO ]: Found error trace [2018-06-25 12:57:12,629 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:57:12,629 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:57:12,629 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 8 times [2018-06-25 12:57:12,629 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:57:12,629 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:57:12,629 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:57:12,629 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:57:12,629 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:57:12,735 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:57:13,056 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:57:13,056 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:57:13,056 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 12:57:13,062 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:57:13,122 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:57:13,122 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:57:13,125 INFO ]: Computing forward predicates... [2018-06-25 12:57:16,236 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:57:16,245 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 12:57:16,246 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:57:22,672 WARN ]: expecting exponential blowup for input size 7 Received shutdown request... [2018-06-25 12:57:37,480 INFO ]: Timeout while computing interpolants [2018-06-25 12:57:37,681 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:57:37,681 WARN ]: Verification canceled [2018-06-25 12:57:37,685 WARN ]: Timeout [2018-06-25 12:57:37,686 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:57:37 BoogieIcfgContainer [2018-06-25 12:57:37,686 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:57:37,686 INFO ]: Toolchain (without parser) took 66683.95 ms. Allocated memory was 308.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 260.7 MB in the beginning and 758.8 MB in the end (delta: -498.1 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:57:37,687 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.3 MB. Free memory is still 272.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:57:37,687 INFO ]: ChcToBoogie took 62.86 ms. Allocated memory is still 308.3 MB. Free memory was 260.7 MB in the beginning and 258.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:57:37,688 INFO ]: Boogie Preprocessor took 50.75 ms. Allocated memory is still 308.3 MB. Free memory was 258.7 MB in the beginning and 256.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:57:37,688 INFO ]: RCFGBuilder took 269.95 ms. Allocated memory is still 308.3 MB. Free memory was 256.7 MB in the beginning and 246.7 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:57:37,689 INFO ]: TraceAbstraction took 66285.16 ms. Allocated memory was 308.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 246.7 MB in the beginning and 758.8 MB in the end (delta: -512.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:57:37,694 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.3 MB. Free memory is still 272.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 62.86 ms. Allocated memory is still 308.3 MB. Free memory was 260.7 MB in the beginning and 258.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 50.75 ms. Allocated memory is still 308.3 MB. Free memory was 258.7 MB in the beginning and 256.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 269.95 ms. Allocated memory is still 308.3 MB. Free memory was 256.7 MB in the beginning and 246.7 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 66285.16 ms. Allocated memory was 308.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 246.7 MB in the beginning and 758.8 MB in the end (delta: -512.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 16 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 1149 quantified variables from 13 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 66.2s OverallTime, 9 OverallIterations, 8 TraceHistogramMax, 4.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 24 SDslu, 168 SDs, 0 SdLazy, 68 SolverSat, 54 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 155 GetRequests, 51 SyntacticMatches, 23 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 218 ImplicationChecksByTransitivity, 7.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=16occurred 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.6s SatisfiabilityAnalysisTime, 35.6s InterpolantComputationTime, 161 NumberOfCodeBlocks, 161 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 146 ConstructedInterpolants, 0 QuantifiedInterpolants, 8781 SizeOfPredicates, 35 NumberOfNonLiveVariables, 1281 ConjunctsInSsa, 289 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/168 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/dillig32.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_12-57-37-704.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig32.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_12-57-37-704.csv Completed graceful shutdown