java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifnat.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:30:44,381 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:30:44,383 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:30:44,399 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:30:44,399 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:30:44,402 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:30:44,403 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:30:44,405 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:30:44,407 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:30:44,407 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:30:44,409 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:30:44,409 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:30:44,410 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:30:44,411 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:30:44,413 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:30:44,414 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:30:44,424 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:30:44,426 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:30:44,427 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:30:44,428 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:30:44,429 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:30:44,435 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:30:44,435 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:30:44,435 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:30:44,436 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:30:44,437 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:30:44,437 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:30:44,440 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:30:44,441 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:30:44,442 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:30:44,442 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:30:44,443 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:30:44,443 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:30:44,449 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:30:44,450 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:30:44,450 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:30:44,472 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:30:44,472 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:30:44,473 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:30:44,473 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:30:44,474 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:30:44,474 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:30:44,474 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:30:44,474 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:30:44,477 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:30:44,477 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:30:44,478 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:30:44,478 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:30:44,478 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:30:44,478 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:30:44,478 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:30:44,478 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:30:44,479 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:30:44,480 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:30:44,480 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:30:44,526 INFO ]: Repository-Root is: /tmp [2018-06-22 05:30:44,545 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:30:44,552 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:30:44,554 INFO ]: Initializing SmtParser... [2018-06-22 05:30:44,555 INFO ]: SmtParser initialized [2018-06-22 05:30:44,555 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifnat.c.smt2 [2018-06-22 05:30:44,557 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 05:30:44,659 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifnat.c.smt2 unknown [2018-06-22 05:30:45,269 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifnat.c.smt2 [2018-06-22 05:30:45,274 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:30:45,282 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:30:45,282 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:30:45,282 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:30:45,283 INFO ]: ChcToBoogie initialized [2018-06-22 05:30:45,286 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:30:45" (1/1) ... [2018-06-22 05:30:45,355 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45 Unit [2018-06-22 05:30:45,355 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:30:45,355 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:30:45,355 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:30:45,355 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:30:45,378 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (1/1) ... [2018-06-22 05:30:45,378 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (1/1) ... [2018-06-22 05:30:45,403 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (1/1) ... [2018-06-22 05:30:45,403 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (1/1) ... [2018-06-22 05:30:45,426 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (1/1) ... [2018-06-22 05:30:45,428 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (1/1) ... [2018-06-22 05:30:45,434 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (1/1) ... [2018-06-22 05:30:45,440 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:30:45,440 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:30:45,440 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:30:45,440 INFO ]: RCFGBuilder initialized [2018-06-22 05:30:45,441 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 05:30:45,456 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:30:45,456 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:30:45,456 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:30:45,456 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:30:45,456 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:30:45,456 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:30:45,961 INFO ]: Using library mode [2018-06-22 05:30:45,961 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:30:45 BoogieIcfgContainer [2018-06-22 05:30:45,961 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:30:45,965 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:30:45,965 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:30:45,968 INFO ]: TraceAbstraction initialized [2018-06-22 05:30:45,969 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:30:45" (1/3) ... [2018-06-22 05:30:45,970 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5b5f84ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:30:45, skipping insertion in model container [2018-06-22 05:30:45,970 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:30:45" (2/3) ... [2018-06-22 05:30:45,970 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5b5f84ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:30:45, skipping insertion in model container [2018-06-22 05:30:45,970 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:30:45" (3/3) ... [2018-06-22 05:30:45,973 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:30:45,982 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:30:45,993 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:30:46,045 INFO ]: Using default assertion order modulation [2018-06-22 05:30:46,046 INFO ]: Interprodecural is true [2018-06-22 05:30:46,046 INFO ]: Hoare is false [2018-06-22 05:30:46,046 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:30:46,046 INFO ]: Backedges is TWOTRACK [2018-06-22 05:30:46,046 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:30:46,046 INFO ]: Difference is false [2018-06-22 05:30:46,046 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:30:46,046 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:30:46,068 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:30:46,082 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:30:46,082 INFO ]: Found error trace [2018-06-22 05:30:46,083 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:30:46,083 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:30:46,088 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-22 05:30:46,090 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:30:46,090 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:30:46,126 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:46,126 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:30:46,126 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:46,178 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:46,345 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:30:46,347 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:30:46,347 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:30:46,348 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:30:46,360 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:30:46,360 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:30:46,363 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:30:46,446 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:30:46,447 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:30:46,447 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:30:46,448 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:30:46,448 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:30:46,457 INFO ]: With dead ends: 9 [2018-06-22 05:30:46,457 INFO ]: Without dead ends: 9 [2018-06-22 05:30:46,458 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-22 05:30:46,472 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:30:46,489 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:30:46,490 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:30:46,491 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:30:46,492 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:30:46,492 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:30:46,492 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:30:46,492 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:30:46,492 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:30:46,493 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:30:46,493 INFO ]: Found error trace [2018-06-22 05:30:46,493 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:30:46,493 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:30:46,493 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-22 05:30:46,493 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:30:46,493 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:30:46,494 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:46,494 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:30:46,494 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:46,649 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:46,913 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:30:46,913 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:30:46,913 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:30:46,927 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:30:47,055 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:47,066 INFO ]: Computing forward predicates... [2018-06-22 05:30:48,718 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:30:48,744 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:30:48,744 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 05:30:48,745 INFO ]: Interpolant automaton has 5 states [2018-06-22 05:30:48,745 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 05:30:48,745 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:30:48,745 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 05:30:48,934 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:30:48,935 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 05:30:48,936 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 05:30:48,936 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 05:30:48,937 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:30:48,937 INFO ]: With dead ends: 10 [2018-06-22 05:30:48,937 INFO ]: Without dead ends: 10 [2018-06-22 05:30:48,938 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:30:48,938 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 05:30:48,939 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 05:30:48,939 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 05:30:48,939 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 05:30:48,939 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 05:30:48,940 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:30:48,940 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 05:30:48,940 INFO ]: Interpolant automaton has 5 states. [2018-06-22 05:30:48,940 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 05:30:48,940 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 05:30:48,940 INFO ]: Found error trace [2018-06-22 05:30:48,940 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:30:48,940 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:30:48,940 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-22 05:30:48,940 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:30:48,940 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:30:48,942 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:48,942 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:30:48,943 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:49,040 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:49,385 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 8 [2018-06-22 05:30:49,535 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:30:49,535 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:30:49,535 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:30:49,542 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:30:49,668 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:30:49,668 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:49,674 INFO ]: Computing forward predicates... [2018-06-22 05:30:50,061 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 7 [2018-06-22 05:30:54,551 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:30:54,574 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:30:54,574 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-22 05:30:54,574 INFO ]: Interpolant automaton has 6 states [2018-06-22 05:30:54,574 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 05:30:54,574 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:30:54,574 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-22 05:30:54,742 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 12 [2018-06-22 05:30:54,765 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:30:54,765 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 05:30:54,766 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 05:30:54,766 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-22 05:30:54,766 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:30:54,767 INFO ]: With dead ends: 11 [2018-06-22 05:30:54,767 INFO ]: Without dead ends: 11 [2018-06-22 05:30:54,767 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=26, Invalid=30, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:30:54,767 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 05:30:54,768 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 05:30:54,768 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 05:30:54,768 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 05:30:54,768 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-22 05:30:54,768 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:30:54,768 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 05:30:54,768 INFO ]: Interpolant automaton has 6 states. [2018-06-22 05:30:54,768 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 05:30:54,768 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 05:30:54,768 INFO ]: Found error trace [2018-06-22 05:30:54,768 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:30:54,768 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:30:54,769 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-22 05:30:54,769 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:30:54,769 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:30:54,769 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:54,769 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:30:54,769 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:30:54,938 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:55,726 WARN ]: Spent 563.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 8 [2018-06-22 05:30:55,892 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 7 [2018-06-22 05:30:55,932 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:30:55,932 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:30:55,932 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:30:55,949 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:30:56,098 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 05:30:56,098 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:30:56,106 INFO ]: Computing forward predicates... [2018-06-22 05:30:57,037 WARN ]: Spent 277.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 9 Received shutdown request... [2018-06-22 05:31:52,093 INFO ]: Timeout while computing interpolants [2018-06-22 05:31:52,294 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:31:52,294 WARN ]: Verification canceled [2018-06-22 05:31:52,298 WARN ]: Timeout [2018-06-22 05:31:52,299 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:31:52 BoogieIcfgContainer [2018-06-22 05:31:52,299 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:31:52,300 INFO ]: Toolchain (without parser) took 67024.79 ms. Allocated memory was 308.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 232.8 MB in the beginning and 1.0 GB in the end (delta: -815.0 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:31:52,301 INFO ]: SmtParser took 0.10 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-22 05:31:52,301 INFO ]: ChcToBoogie took 72.77 ms. Allocated memory is still 308.3 MB. Free memory was 232.8 MB in the beginning and 228.8 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:31:52,301 INFO ]: Boogie Preprocessor took 84.37 ms. Allocated memory is still 308.3 MB. Free memory was 228.8 MB in the beginning and 226.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:31:52,302 INFO ]: RCFGBuilder took 521.25 ms. Allocated memory is still 308.3 MB. Free memory was 226.8 MB in the beginning and 198.5 MB in the end (delta: 28.3 MB). Peak memory consumption was 28.3 MB. Max. memory is 3.6 GB. [2018-06-22 05:31:52,302 INFO ]: TraceAbstraction took 66333.53 ms. Allocated memory was 308.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 198.5 MB in the beginning and 1.0 GB in the end (delta: -849.3 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 05:31:52,307 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.10 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 72.77 ms. Allocated memory is still 308.3 MB. Free memory was 232.8 MB in the beginning and 228.8 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 84.37 ms. Allocated memory is still 308.3 MB. Free memory was 228.8 MB in the beginning and 226.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 521.25 ms. Allocated memory is still 308.3 MB. Free memory was 226.8 MB in the beginning and 198.5 MB in the end (delta: 28.3 MB). Peak memory consumption was 28.3 MB. Max. memory is 3.6 GB. * TraceAbstraction took 66333.53 ms. Allocated memory was 308.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 198.5 MB in the beginning and 1.0 GB in the end (delta: -849.3 MB). Peak memory consumption was 1.2 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 11 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 22 quantified variables from 81 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 66.2s OverallTime, 4 OverallIterations, 3 TraceHistogramMax, 0.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 1 SDslu, 34 SDs, 0 SdLazy, 17 SolverSat, 4 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 30 GetRequests, 16 SyntacticMatches, 3 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 1.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=11occurred in iteration=3, 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, 3 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 7.4s InterpolantComputationTime, 41 NumberOfCodeBlocks, 41 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 36 ConstructedInterpolants, 0 QuantifiedInterpolants, 746 SizeOfPredicates, 14 NumberOfNonLiveVariables, 632 ConjunctsInSsa, 50 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 0/8 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/lifnat.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-31-52-319.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lifnat.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-31-52-319.csv Completed graceful shutdown