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/eldarica-misc/LIA/Consistency/fortune-half.23.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 00:39:50,677 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 00:39:50,679 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 00:39:50,692 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 00:39:50,692 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 00:39:50,693 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 00:39:50,695 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 00:39:50,699 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 00:39:50,700 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 00:39:50,701 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 00:39:50,703 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 00:39:50,703 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 00:39:50,704 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 00:39:50,705 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 00:39:50,706 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 00:39:50,709 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 00:39:50,711 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 00:39:50,715 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 00:39:50,717 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 00:39:50,717 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 00:39:50,719 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 00:39:50,721 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 00:39:50,721 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 00:39:50,721 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 00:39:50,722 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 00:39:50,723 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 00:39:50,724 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 00:39:50,724 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 00:39:50,725 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 00:39:50,726 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 00:39:50,726 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 00:39:50,727 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 00:39:50,727 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 00:39:50,728 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 00:39:50,729 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 00:39:50,729 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 00:39:50,745 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 00:39:50,746 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 00:39:50,746 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 00:39:50,746 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 00:39:50,747 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 00:39:50,747 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 00:39:50,748 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 00:39:50,748 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 00:39:50,748 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 00:39:50,748 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 00:39:50,748 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 00:39:50,748 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 00:39:50,749 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 00:39:50,749 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 00:39:50,749 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 00:39:50,749 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 00:39:50,749 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 00:39:50,751 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 00:39:50,751 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 00:39:50,794 INFO ]: Repository-Root is: /tmp [2018-06-22 00:39:50,810 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 00:39:50,815 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 00:39:50,817 INFO ]: Initializing SmtParser... [2018-06-22 00:39:50,817 INFO ]: SmtParser initialized [2018-06-22 00:39:50,818 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/Consistency/fortune-half.23.smt2 [2018-06-22 00:39:50,819 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 00:39:50,910 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/fortune-half.23.smt2 unknown [2018-06-22 00:39:51,364 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/fortune-half.23.smt2 [2018-06-22 00:39:51,378 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 00:39:51,383 INFO ]: Walking toolchain with 4 elements. [2018-06-22 00:39:51,384 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 00:39:51,384 INFO ]: Initializing ChcToBoogie... [2018-06-22 00:39:51,384 INFO ]: ChcToBoogie initialized [2018-06-22 00:39:51,387 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 12:39:51" (1/1) ... [2018-06-22 00:39:51,535 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51 Unit [2018-06-22 00:39:51,535 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 00:39:51,536 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 00:39:51,536 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 00:39:51,536 INFO ]: Boogie Preprocessor initialized [2018-06-22 00:39:51,559 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (1/1) ... [2018-06-22 00:39:51,559 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (1/1) ... [2018-06-22 00:39:51,574 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (1/1) ... [2018-06-22 00:39:51,574 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (1/1) ... [2018-06-22 00:39:51,594 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (1/1) ... [2018-06-22 00:39:51,607 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (1/1) ... [2018-06-22 00:39:51,611 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (1/1) ... [2018-06-22 00:39:51,624 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 00:39:51,625 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 00:39:51,625 INFO ]: Initializing RCFGBuilder... [2018-06-22 00:39:51,625 INFO ]: RCFGBuilder initialized [2018-06-22 00:39:51,626 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (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 00:39:51,651 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 00:39:51,651 INFO ]: Found specification of procedure gotoProc [2018-06-22 00:39:51,651 INFO ]: Found implementation of procedure gotoProc [2018-06-22 00:39:51,651 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 00:39:51,651 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 00:39:51,651 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 00:39:53,286 INFO ]: Using library mode [2018-06-22 00:39:53,287 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 12:39:53 BoogieIcfgContainer [2018-06-22 00:39:53,287 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 00:39:53,288 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 00:39:53,288 INFO ]: Initializing TraceAbstraction... [2018-06-22 00:39:53,296 INFO ]: TraceAbstraction initialized [2018-06-22 00:39:53,296 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 12:39:51" (1/3) ... [2018-06-22 00:39:53,297 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61209605 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 12:39:53, skipping insertion in model container [2018-06-22 00:39:53,297 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:39:51" (2/3) ... [2018-06-22 00:39:53,297 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61209605 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 12:39:53, skipping insertion in model container [2018-06-22 00:39:53,297 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 12:39:53" (3/3) ... [2018-06-22 00:39:53,299 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 00:39:53,305 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 00:39:53,315 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 00:39:53,360 INFO ]: Using default assertion order modulation [2018-06-22 00:39:53,360 INFO ]: Interprodecural is true [2018-06-22 00:39:53,360 INFO ]: Hoare is false [2018-06-22 00:39:53,360 INFO ]: Compute interpolants for FPandBP [2018-06-22 00:39:53,360 INFO ]: Backedges is TWOTRACK [2018-06-22 00:39:53,360 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 00:39:53,361 INFO ]: Difference is false [2018-06-22 00:39:53,361 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 00:39:53,361 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 00:39:53,379 INFO ]: Start isEmpty. Operand 146 states. [2018-06-22 00:39:53,404 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 00:39:53,404 INFO ]: Found error trace [2018-06-22 00:39:53,406 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:39:53,406 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:39:53,410 INFO ]: Analyzing trace with hash 1498302052, now seen corresponding path program 1 times [2018-06-22 00:39:53,411 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:39:53,412 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:39:53,456 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:39:53,456 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:39:53,456 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:39:53,507 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:39:53,761 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 00:39:53,765 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 00:39:53,765 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 00:39:53,767 INFO ]: Interpolant automaton has 4 states [2018-06-22 00:39:53,782 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 00:39:53,782 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 00:39:53,785 INFO ]: Start difference. First operand 146 states. Second operand 4 states. [2018-06-22 00:39:56,486 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 00:39:56,486 INFO ]: Finished difference Result 285 states and 555 transitions. [2018-06-22 00:39:56,486 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 00:39:56,487 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-22 00:39:56,487 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 00:39:56,539 INFO ]: With dead ends: 285 [2018-06-22 00:39:56,539 INFO ]: Without dead ends: 275 [2018-06-22 00:39:56,541 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 00:39:56,559 INFO ]: Start minimizeSevpa. Operand 275 states. [2018-06-22 00:39:56,680 INFO ]: Finished minimizeSevpa. Reduced states from 275 to 275. [2018-06-22 00:39:56,681 INFO ]: Start removeUnreachable. Operand 275 states. [2018-06-22 00:39:56,718 INFO ]: Finished removeUnreachable. Reduced from 275 states to 275 states and 537 transitions. [2018-06-22 00:39:56,721 INFO ]: Start accepts. Automaton has 275 states and 537 transitions. Word has length 8 [2018-06-22 00:39:56,722 INFO ]: Finished accepts. word is rejected. [2018-06-22 00:39:56,722 INFO ]: Abstraction has 275 states and 537 transitions. [2018-06-22 00:39:56,722 INFO ]: Interpolant automaton has 4 states. [2018-06-22 00:39:56,722 INFO ]: Start isEmpty. Operand 275 states and 537 transitions. [2018-06-22 00:39:56,730 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 00:39:56,730 INFO ]: Found error trace [2018-06-22 00:39:56,730 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:39:56,730 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:39:56,730 INFO ]: Analyzing trace with hash 1359982439, now seen corresponding path program 1 times [2018-06-22 00:39:56,730 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:39:56,730 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:39:56,731 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:39:56,731 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:39:56,731 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:39:56,741 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:39:56,889 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 00:39:56,889 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 00:39:56,889 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 00:39:56,891 INFO ]: Interpolant automaton has 4 states [2018-06-22 00:39:56,891 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 00:39:56,891 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 00:39:56,891 INFO ]: Start difference. First operand 275 states and 537 transitions. Second operand 4 states. [2018-06-22 00:39:58,651 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 00:39:58,651 INFO ]: Finished difference Result 411 states and 804 transitions. [2018-06-22 00:39:58,652 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 00:39:58,652 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-22 00:39:58,652 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 00:39:58,677 INFO ]: With dead ends: 411 [2018-06-22 00:39:58,677 INFO ]: Without dead ends: 411 [2018-06-22 00:39:58,678 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 00:39:58,679 INFO ]: Start minimizeSevpa. Operand 411 states. [2018-06-22 00:39:58,799 INFO ]: Finished minimizeSevpa. Reduced states from 411 to 411. [2018-06-22 00:39:58,799 INFO ]: Start removeUnreachable. Operand 411 states. [2018-06-22 00:39:58,815 INFO ]: Finished removeUnreachable. Reduced from 411 states to 411 states and 804 transitions. [2018-06-22 00:39:58,815 INFO ]: Start accepts. Automaton has 411 states and 804 transitions. Word has length 8 [2018-06-22 00:39:58,815 INFO ]: Finished accepts. word is rejected. [2018-06-22 00:39:58,815 INFO ]: Abstraction has 411 states and 804 transitions. [2018-06-22 00:39:58,815 INFO ]: Interpolant automaton has 4 states. [2018-06-22 00:39:58,815 INFO ]: Start isEmpty. Operand 411 states and 804 transitions. [2018-06-22 00:39:58,834 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 00:39:58,834 INFO ]: Found error trace [2018-06-22 00:39:58,834 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:39:58,834 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:39:58,835 INFO ]: Analyzing trace with hash -1949098590, now seen corresponding path program 1 times [2018-06-22 00:39:58,835 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:39:58,835 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:39:58,835 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:39:58,835 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:39:58,835 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:39:58,877 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:39:59,012 INFO ]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 00:39:59,013 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 00:39:59,013 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 00:39:59,013 INFO ]: Interpolant automaton has 7 states [2018-06-22 00:39:59,013 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 00:39:59,013 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 00:39:59,013 INFO ]: Start difference. First operand 411 states and 804 transitions. Second operand 7 states. [2018-06-22 00:40:12,936 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 00:40:12,936 INFO ]: Finished difference Result 1773 states and 11631 transitions. [2018-06-22 00:40:12,936 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 00:40:12,936 INFO ]: Start accepts. Automaton has 7 states. Word has length 18 [2018-06-22 00:40:12,936 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 00:40:13,741 INFO ]: With dead ends: 1773 [2018-06-22 00:40:13,741 INFO ]: Without dead ends: 1773 [2018-06-22 00:40:13,741 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=87, Invalid=255, Unknown=0, NotChecked=0, Total=342 [2018-06-22 00:40:13,743 INFO ]: Start minimizeSevpa. Operand 1773 states. [2018-06-22 00:40:14,988 INFO ]: Finished minimizeSevpa. Reduced states from 1773 to 884. [2018-06-22 00:40:14,988 INFO ]: Start removeUnreachable. Operand 884 states. [2018-06-22 00:40:15,045 INFO ]: Finished removeUnreachable. Reduced from 884 states to 884 states and 2303 transitions. [2018-06-22 00:40:15,045 INFO ]: Start accepts. Automaton has 884 states and 2303 transitions. Word has length 18 [2018-06-22 00:40:15,045 INFO ]: Finished accepts. word is rejected. [2018-06-22 00:40:15,045 INFO ]: Abstraction has 884 states and 2303 transitions. [2018-06-22 00:40:15,045 INFO ]: Interpolant automaton has 7 states. [2018-06-22 00:40:15,045 INFO ]: Start isEmpty. Operand 884 states and 2303 transitions. [2018-06-22 00:40:15,075 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 00:40:15,075 INFO ]: Found error trace [2018-06-22 00:40:15,075 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:40:15,076 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:40:15,076 INFO ]: Analyzing trace with hash -1080279009, now seen corresponding path program 1 times [2018-06-22 00:40:15,076 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:40:15,076 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:40:15,077 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:40:15,077 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:40:15,077 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:40:15,131 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:40:15,619 INFO ]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 00:40:15,619 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 00:40:15,619 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 00:40:15,619 INFO ]: Interpolant automaton has 7 states [2018-06-22 00:40:15,619 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 00:40:15,619 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 00:40:15,620 INFO ]: Start difference. First operand 884 states and 2303 transitions. Second operand 7 states. [2018-06-22 00:40:16,762 WARN ]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 00:40:24,510 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 00:40:24,510 INFO ]: Finished difference Result 3471 states and 31741 transitions. [2018-06-22 00:40:24,510 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 00:40:24,510 INFO ]: Start accepts. Automaton has 7 states. Word has length 18 [2018-06-22 00:40:24,510 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 00:40:26,451 INFO ]: With dead ends: 3471 [2018-06-22 00:40:26,451 INFO ]: Without dead ends: 3471 [2018-06-22 00:40:26,451 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2018-06-22 00:40:26,454 INFO ]: Start minimizeSevpa. Operand 3471 states. [2018-06-22 00:40:31,642 INFO ]: Finished minimizeSevpa. Reduced states from 3471 to 2461. [2018-06-22 00:40:31,643 INFO ]: Start removeUnreachable. Operand 2461 states. [2018-06-22 00:40:31,885 INFO ]: Finished removeUnreachable. Reduced from 2461 states to 2461 states and 9262 transitions. [2018-06-22 00:40:31,886 INFO ]: Start accepts. Automaton has 2461 states and 9262 transitions. Word has length 18 [2018-06-22 00:40:31,886 INFO ]: Finished accepts. word is rejected. [2018-06-22 00:40:31,886 INFO ]: Abstraction has 2461 states and 9262 transitions. [2018-06-22 00:40:31,886 INFO ]: Interpolant automaton has 7 states. [2018-06-22 00:40:31,886 INFO ]: Start isEmpty. Operand 2461 states and 9262 transitions. [2018-06-22 00:40:31,925 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 00:40:31,925 INFO ]: Found error trace [2018-06-22 00:40:31,925 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:40:31,925 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:40:31,927 INFO ]: Analyzing trace with hash 980580793, now seen corresponding path program 1 times [2018-06-22 00:40:31,927 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:40:31,927 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:40:31,928 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:40:31,928 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:40:31,928 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:40:31,963 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:40:32,130 INFO ]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 00:40:32,130 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 00:40:32,130 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 00:40:32,137 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:40:32,191 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:40:32,208 INFO ]: Computing forward predicates... [2018-06-22 00:40:32,663 INFO ]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 00:40:32,685 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 00:40:32,686 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-22 00:40:32,686 INFO ]: Interpolant automaton has 12 states [2018-06-22 00:40:32,686 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 00:40:32,686 INFO ]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-06-22 00:40:32,686 INFO ]: Start difference. First operand 2461 states and 9262 transitions. Second operand 12 states. [2018-06-22 00:40:33,007 WARN ]: Spent 164.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 10 [2018-06-22 00:40:33,169 WARN ]: Spent 140.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 20 [2018-06-22 00:40:33,493 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 14 Received shutdown request... [2018-06-22 00:40:50,055 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-06-22 00:40:50,067 WARN ]: Verification canceled [2018-06-22 00:40:50,071 WARN ]: Timeout [2018-06-22 00:40:50,071 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 12:40:50 BoogieIcfgContainer [2018-06-22 00:40:50,071 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 00:40:50,072 INFO ]: Toolchain (without parser) took 58693.66 ms. Allocated memory was 307.8 MB in the beginning and 1.7 GB in the end (delta: 1.3 GB). Free memory was 249.2 MB in the beginning and 1.2 GB in the end (delta: -904.0 MB). Peak memory consumption was 440.8 MB. Max. memory is 3.6 GB. [2018-06-22 00:40:50,073 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 307.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 00:40:50,073 INFO ]: ChcToBoogie took 151.67 ms. Allocated memory is still 307.8 MB. Free memory was 249.2 MB in the beginning and 245.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-22 00:40:50,074 INFO ]: Boogie Preprocessor took 88.71 ms. Allocated memory is still 307.8 MB. Free memory was 245.2 MB in the beginning and 243.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 00:40:50,074 INFO ]: RCFGBuilder took 1661.82 ms. Allocated memory was 307.8 MB in the beginning and 327.7 MB in the end (delta: 19.9 MB). Free memory was 242.2 MB in the beginning and 283.2 MB in the end (delta: -41.0 MB). Peak memory consumption was 61.7 MB. Max. memory is 3.6 GB. [2018-06-22 00:40:50,075 INFO ]: TraceAbstraction took 56783.04 ms. Allocated memory was 327.7 MB in the beginning and 1.7 GB in the end (delta: 1.3 GB). Free memory was 283.2 MB in the beginning and 1.2 GB in the end (delta: -870.1 MB). Peak memory consumption was 454.8 MB. Max. memory is 3.6 GB. [2018-06-22 00:40:50,078 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 307.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 151.67 ms. Allocated memory is still 307.8 MB. Free memory was 249.2 MB in the beginning and 245.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 88.71 ms. Allocated memory is still 307.8 MB. Free memory was 245.2 MB in the beginning and 243.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 1661.82 ms. Allocated memory was 307.8 MB in the beginning and 327.7 MB in the end (delta: 19.9 MB). Free memory was 242.2 MB in the beginning and 283.2 MB in the end (delta: -41.0 MB). Peak memory consumption was 61.7 MB. Max. memory is 3.6 GB. * TraceAbstraction took 56783.04 ms. Allocated memory was 327.7 MB in the beginning and 1.7 GB in the end (delta: 1.3 GB). Free memory was 283.2 MB in the beginning and 1.2 GB in the end (delta: -870.1 MB). Peak memory consumption was 454.8 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (2461states) and interpolant automaton (currently 45 states, 12 states before enhancement), while ReachableStatesComputation was computing reachable states (3114 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 146 locations, 1 error locations. TIMEOUT Result, 56.7s OverallTime, 5 OverallIterations, 2 TraceHistogramMax, 47.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 3963 SDtfs, 1436 SDslu, 8968 SDs, 0 SdLazy, 28177 SolverSat, 10479 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 36.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 106 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 732 ImplicationChecksByTransitivity, 3.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=2461occurred in iteration=4, 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: 7.0s AutomataMinimizationTime, 4 MinimizatonAttempts, 1899 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 1.6s InterpolantComputationTime, 88 NumberOfCodeBlocks, 88 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 82 ConstructedInterpolants, 0 QuantifiedInterpolants, 3298 SizeOfPredicates, 7 NumberOfNonLiveVariables, 293 ConjunctsInSsa, 11 ConjunctsInUnsatCore, 6 InterpolantComputations, 4 PerfectInterpolantSequences, 16/18 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/fortune-half.23.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_00-40-50-092.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/fortune-half.23.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_00-40-50-092.csv Completed graceful shutdown