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/llreve-bench/smt2/rec__mccarthy91.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 02:31:51,414 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 02:31:51,416 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 02:31:51,430 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 02:31:51,430 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 02:31:51,431 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 02:31:51,432 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 02:31:51,435 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 02:31:51,437 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 02:31:51,437 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 02:31:51,438 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 02:31:51,439 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 02:31:51,439 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 02:31:51,441 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 02:31:51,441 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 02:31:51,442 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 02:31:51,444 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 02:31:51,446 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 02:31:51,448 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 02:31:51,449 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 02:31:51,450 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 02:31:51,452 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 02:31:51,453 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 02:31:51,453 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 02:31:51,454 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 02:31:51,455 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 02:31:51,455 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 02:31:51,456 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 02:31:51,457 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 02:31:51,457 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 02:31:51,458 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 02:31:51,459 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 02:31:51,459 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 02:31:51,460 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 02:31:51,461 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 02:31:51,461 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 02:31:51,475 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 02:31:51,475 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 02:31:51,475 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 02:31:51,476 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 02:31:51,477 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 02:31:51,477 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 02:31:51,477 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 02:31:51,477 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 02:31:51,478 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 02:31:51,478 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 02:31:51,478 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 02:31:51,478 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 02:31:51,478 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 02:31:51,479 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 02:31:51,479 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 02:31:51,479 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 02:31:51,479 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 02:31:51,481 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 02:31:51,481 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 02:31:51,526 INFO ]: Repository-Root is: /tmp [2018-06-22 02:31:51,544 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 02:31:51,548 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 02:31:51,549 INFO ]: Initializing SmtParser... [2018-06-22 02:31:51,549 INFO ]: SmtParser initialized [2018-06-22 02:31:51,550 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/llreve-bench/smt2/rec__mccarthy91.smt2 [2018-06-22 02:31:51,552 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 02:31:51,641 INFO ]: Executing SMT file /storage/chc-comp/llreve-bench/smt2/rec__mccarthy91.smt2 unknown de.uni_freiburg.informatik.ultimate.plugins.generator.treeautomizer.parsing.HornClauseParserScript$1@572b1f06 [2018-06-22 02:31:51,823 INFO ]: Succesfully executed SMT file /storage/chc-comp/llreve-bench/smt2/rec__mccarthy91.smt2 [2018-06-22 02:31:51,828 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 02:31:51,833 INFO ]: Walking toolchain with 4 elements. [2018-06-22 02:31:51,834 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 02:31:51,834 INFO ]: Initializing ChcToBoogie... [2018-06-22 02:31:51,834 INFO ]: ChcToBoogie initialized [2018-06-22 02:31:51,838 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:31:51" (1/1) ... [2018-06-22 02:31:51,896 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51 Unit [2018-06-22 02:31:51,897 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 02:31:51,897 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 02:31:51,897 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 02:31:51,897 INFO ]: Boogie Preprocessor initialized [2018-06-22 02:31:51,920 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51" (1/1) ... [2018-06-22 02:31:51,921 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51" (1/1) ... [2018-06-22 02:31:51,929 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51" (1/1) ... [2018-06-22 02:31:51,929 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51" (1/1) ... [2018-06-22 02:31:51,935 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51" (1/1) ... [2018-06-22 02:31:51,949 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51" (1/1) ... [2018-06-22 02:31:51,953 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51" (1/1) ... [2018-06-22 02:31:51,955 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 02:31:51,956 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 02:31:51,956 INFO ]: Initializing RCFGBuilder... [2018-06-22 02:31:51,956 INFO ]: RCFGBuilder initialized [2018-06-22 02:31:51,957 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31: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 02:31:51,986 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 02:31:51,986 INFO ]: Found specification of procedure gotoProc [2018-06-22 02:31:51,986 INFO ]: Found implementation of procedure gotoProc [2018-06-22 02:31:51,986 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 02:31:51,986 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 02:31:51,986 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 02:31:52,662 INFO ]: Using library mode [2018-06-22 02:31:52,663 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:31:52 BoogieIcfgContainer [2018-06-22 02:31:52,663 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 02:31:52,665 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 02:31:52,665 INFO ]: Initializing TraceAbstraction... [2018-06-22 02:31:52,668 INFO ]: TraceAbstraction initialized [2018-06-22 02:31:52,668 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:31:51" (1/3) ... [2018-06-22 02:31:52,669 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@287a132c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 02:31:52, skipping insertion in model container [2018-06-22 02:31:52,669 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:51" (2/3) ... [2018-06-22 02:31:52,669 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@287a132c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 02:31:52, skipping insertion in model container [2018-06-22 02:31:52,669 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:31:52" (3/3) ... [2018-06-22 02:31:52,671 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 02:31:52,680 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 02:31:52,691 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 02:31:52,735 INFO ]: Using default assertion order modulation [2018-06-22 02:31:52,736 INFO ]: Interprodecural is true [2018-06-22 02:31:52,736 INFO ]: Hoare is false [2018-06-22 02:31:52,736 INFO ]: Compute interpolants for FPandBP [2018-06-22 02:31:52,736 INFO ]: Backedges is TWOTRACK [2018-06-22 02:31:52,736 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 02:31:52,736 INFO ]: Difference is false [2018-06-22 02:31:52,736 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 02:31:52,736 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 02:31:52,756 INFO ]: Start isEmpty. Operand 52 states. [2018-06-22 02:31:52,767 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 02:31:52,767 INFO ]: Found error trace [2018-06-22 02:31:52,768 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:31:52,768 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:31:52,774 INFO ]: Analyzing trace with hash 1382216873, now seen corresponding path program 1 times [2018-06-22 02:31:52,776 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:31:52,777 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:31:52,817 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:52,817 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:31:52,817 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:52,879 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:31:52,937 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 02:31:52,940 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 02:31:52,940 INFO ]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-06-22 02:31:52,942 INFO ]: Interpolant automaton has 2 states [2018-06-22 02:31:52,960 INFO ]: Constructing interpolant automaton starting with 2 interpolants. [2018-06-22 02:31:52,961 INFO ]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-06-22 02:31:52,964 INFO ]: Start difference. First operand 52 states. Second operand 2 states. [2018-06-22 02:31:53,010 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:31:53,010 INFO ]: Finished difference Result 46 states and 81 transitions. [2018-06-22 02:31:53,010 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-06-22 02:31:53,011 INFO ]: Start accepts. Automaton has 2 states. Word has length 7 [2018-06-22 02:31:53,012 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:31:53,031 INFO ]: With dead ends: 46 [2018-06-22 02:31:53,031 INFO ]: Without dead ends: 46 [2018-06-22 02:31:53,033 INFO ]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-06-22 02:31:53,050 INFO ]: Start minimizeSevpa. Operand 46 states. [2018-06-22 02:31:53,085 INFO ]: Finished minimizeSevpa. Reduced states from 46 to 46. [2018-06-22 02:31:53,086 INFO ]: Start removeUnreachable. Operand 46 states. [2018-06-22 02:31:53,091 INFO ]: Finished removeUnreachable. Reduced from 46 states to 46 states and 81 transitions. [2018-06-22 02:31:53,092 INFO ]: Start accepts. Automaton has 46 states and 81 transitions. Word has length 7 [2018-06-22 02:31:53,093 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:31:53,093 INFO ]: Abstraction has 46 states and 81 transitions. [2018-06-22 02:31:53,093 INFO ]: Interpolant automaton has 2 states. [2018-06-22 02:31:53,093 INFO ]: Start isEmpty. Operand 46 states and 81 transitions. [2018-06-22 02:31:53,096 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 02:31:53,096 INFO ]: Found error trace [2018-06-22 02:31:53,096 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:31:53,096 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:31:53,096 INFO ]: Analyzing trace with hash -100393040, now seen corresponding path program 1 times [2018-06-22 02:31:53,096 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:31:53,096 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:31:53,097 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:53,097 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:31:53,097 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:53,105 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:31:53,207 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 02:31:53,207 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 02:31:53,207 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 02:31:53,209 INFO ]: Interpolant automaton has 4 states [2018-06-22 02:31:53,209 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 02:31:53,209 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 02:31:53,209 INFO ]: Start difference. First operand 46 states and 81 transitions. Second operand 4 states. [2018-06-22 02:31:54,238 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:31:54,239 INFO ]: Finished difference Result 89 states and 159 transitions. [2018-06-22 02:31:54,239 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 02:31:54,239 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-22 02:31:54,239 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:31:54,253 INFO ]: With dead ends: 89 [2018-06-22 02:31:54,253 INFO ]: Without dead ends: 89 [2018-06-22 02:31:54,254 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 02:31:54,254 INFO ]: Start minimizeSevpa. Operand 89 states. [2018-06-22 02:31:54,288 INFO ]: Finished minimizeSevpa. Reduced states from 89 to 89. [2018-06-22 02:31:54,288 INFO ]: Start removeUnreachable. Operand 89 states. [2018-06-22 02:31:54,294 INFO ]: Finished removeUnreachable. Reduced from 89 states to 89 states and 159 transitions. [2018-06-22 02:31:54,294 INFO ]: Start accepts. Automaton has 89 states and 159 transitions. Word has length 8 [2018-06-22 02:31:54,294 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:31:54,294 INFO ]: Abstraction has 89 states and 159 transitions. [2018-06-22 02:31:54,294 INFO ]: Interpolant automaton has 4 states. [2018-06-22 02:31:54,294 INFO ]: Start isEmpty. Operand 89 states and 159 transitions. [2018-06-22 02:31:54,298 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 02:31:54,298 INFO ]: Found error trace [2018-06-22 02:31:54,298 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:31:54,298 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:31:54,299 INFO ]: Analyzing trace with hash 446193204, now seen corresponding path program 1 times [2018-06-22 02:31:54,299 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:31:54,299 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:31:54,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:54,299 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:31:54,300 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:54,306 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:31:54,361 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 02:31:54,361 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 02:31:54,361 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 02:31:54,361 INFO ]: Interpolant automaton has 4 states [2018-06-22 02:31:54,361 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 02:31:54,361 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 02:31:54,362 INFO ]: Start difference. First operand 89 states and 159 transitions. Second operand 4 states. [2018-06-22 02:31:54,950 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:31:54,950 INFO ]: Finished difference Result 123 states and 220 transitions. [2018-06-22 02:31:54,951 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 02:31:54,951 INFO ]: Start accepts. Automaton has 4 states. Word has length 10 [2018-06-22 02:31:54,951 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:31:54,965 INFO ]: With dead ends: 123 [2018-06-22 02:31:54,965 INFO ]: Without dead ends: 123 [2018-06-22 02:31:54,965 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 02:31:54,966 INFO ]: Start minimizeSevpa. Operand 123 states. [2018-06-22 02:31:54,984 INFO ]: Finished minimizeSevpa. Reduced states from 123 to 123. [2018-06-22 02:31:54,984 INFO ]: Start removeUnreachable. Operand 123 states. [2018-06-22 02:31:54,989 INFO ]: Finished removeUnreachable. Reduced from 123 states to 123 states and 220 transitions. [2018-06-22 02:31:54,990 INFO ]: Start accepts. Automaton has 123 states and 220 transitions. Word has length 10 [2018-06-22 02:31:54,990 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:31:54,990 INFO ]: Abstraction has 123 states and 220 transitions. [2018-06-22 02:31:54,990 INFO ]: Interpolant automaton has 4 states. [2018-06-22 02:31:54,990 INFO ]: Start isEmpty. Operand 123 states and 220 transitions. [2018-06-22 02:31:54,994 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 02:31:54,994 INFO ]: Found error trace [2018-06-22 02:31:54,994 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:31:54,994 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:31:54,994 INFO ]: Analyzing trace with hash -1156115731, now seen corresponding path program 1 times [2018-06-22 02:31:54,994 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:31:54,994 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:31:54,995 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:54,995 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:31:54,995 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:55,001 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:31:55,028 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 02:31:55,029 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 02:31:55,029 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 02:31:55,029 INFO ]: Interpolant automaton has 4 states [2018-06-22 02:31:55,029 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 02:31:55,029 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 02:31:55,029 INFO ]: Start difference. First operand 123 states and 220 transitions. Second operand 4 states. [2018-06-22 02:31:55,613 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:31:55,614 INFO ]: Finished difference Result 157 states and 281 transitions. [2018-06-22 02:31:55,614 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 02:31:55,614 INFO ]: Start accepts. Automaton has 4 states. Word has length 10 [2018-06-22 02:31:55,614 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:31:55,619 INFO ]: With dead ends: 157 [2018-06-22 02:31:55,619 INFO ]: Without dead ends: 157 [2018-06-22 02:31:55,619 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 02:31:55,620 INFO ]: Start minimizeSevpa. Operand 157 states. [2018-06-22 02:31:55,642 INFO ]: Finished minimizeSevpa. Reduced states from 157 to 157. [2018-06-22 02:31:55,642 INFO ]: Start removeUnreachable. Operand 157 states. [2018-06-22 02:31:55,647 INFO ]: Finished removeUnreachable. Reduced from 157 states to 157 states and 281 transitions. [2018-06-22 02:31:55,647 INFO ]: Start accepts. Automaton has 157 states and 281 transitions. Word has length 10 [2018-06-22 02:31:55,647 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:31:55,647 INFO ]: Abstraction has 157 states and 281 transitions. [2018-06-22 02:31:55,647 INFO ]: Interpolant automaton has 4 states. [2018-06-22 02:31:55,647 INFO ]: Start isEmpty. Operand 157 states and 281 transitions. [2018-06-22 02:31:55,651 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 02:31:55,651 INFO ]: Found error trace [2018-06-22 02:31:55,651 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:31:55,651 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:31:55,651 INFO ]: Analyzing trace with hash 1640032627, now seen corresponding path program 1 times [2018-06-22 02:31:55,651 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:31:55,651 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:31:55,652 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:55,652 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:31:55,652 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:55,656 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:31:55,695 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 02:31:55,696 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 02:31:55,696 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 02:31:55,696 INFO ]: Interpolant automaton has 4 states [2018-06-22 02:31:55,696 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 02:31:55,696 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 02:31:55,696 INFO ]: Start difference. First operand 157 states and 281 transitions. Second operand 4 states. [2018-06-22 02:31:55,902 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:31:55,902 INFO ]: Finished difference Result 191 states and 342 transitions. [2018-06-22 02:31:55,902 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 02:31:55,903 INFO ]: Start accepts. Automaton has 4 states. Word has length 11 [2018-06-22 02:31:55,903 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:31:55,911 INFO ]: With dead ends: 191 [2018-06-22 02:31:55,911 INFO ]: Without dead ends: 191 [2018-06-22 02:31:55,912 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 02:31:55,912 INFO ]: Start minimizeSevpa. Operand 191 states. [2018-06-22 02:31:55,930 INFO ]: Finished minimizeSevpa. Reduced states from 191 to 191. [2018-06-22 02:31:55,931 INFO ]: Start removeUnreachable. Operand 191 states. [2018-06-22 02:31:55,936 INFO ]: Finished removeUnreachable. Reduced from 191 states to 191 states and 342 transitions. [2018-06-22 02:31:55,936 INFO ]: Start accepts. Automaton has 191 states and 342 transitions. Word has length 11 [2018-06-22 02:31:55,936 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:31:55,936 INFO ]: Abstraction has 191 states and 342 transitions. [2018-06-22 02:31:55,936 INFO ]: Interpolant automaton has 4 states. [2018-06-22 02:31:55,936 INFO ]: Start isEmpty. Operand 191 states and 342 transitions. [2018-06-22 02:31:55,942 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 02:31:55,943 INFO ]: Found error trace [2018-06-22 02:31:55,943 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:31:55,943 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:31:55,943 INFO ]: Analyzing trace with hash -102871275, now seen corresponding path program 1 times [2018-06-22 02:31:55,943 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:31:55,943 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:31:55,944 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:55,944 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:31:55,944 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:55,950 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:31:56,074 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 02:31:56,074 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 02:31:56,074 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 02:31:56,075 INFO ]: Interpolant automaton has 4 states [2018-06-22 02:31:56,075 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 02:31:56,075 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 02:31:56,075 INFO ]: Start difference. First operand 191 states and 342 transitions. Second operand 4 states. [2018-06-22 02:31:56,530 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:31:56,530 INFO ]: Finished difference Result 225 states and 403 transitions. [2018-06-22 02:31:56,531 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 02:31:56,531 INFO ]: Start accepts. Automaton has 4 states. Word has length 13 [2018-06-22 02:31:56,531 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:31:56,540 INFO ]: With dead ends: 225 [2018-06-22 02:31:56,540 INFO ]: Without dead ends: 225 [2018-06-22 02:31:56,540 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 02:31:56,540 INFO ]: Start minimizeSevpa. Operand 225 states. [2018-06-22 02:31:56,560 INFO ]: Finished minimizeSevpa. Reduced states from 225 to 225. [2018-06-22 02:31:56,561 INFO ]: Start removeUnreachable. Operand 225 states. [2018-06-22 02:31:56,567 INFO ]: Finished removeUnreachable. Reduced from 225 states to 225 states and 403 transitions. [2018-06-22 02:31:56,567 INFO ]: Start accepts. Automaton has 225 states and 403 transitions. Word has length 13 [2018-06-22 02:31:56,568 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:31:56,568 INFO ]: Abstraction has 225 states and 403 transitions. [2018-06-22 02:31:56,568 INFO ]: Interpolant automaton has 4 states. [2018-06-22 02:31:56,568 INFO ]: Start isEmpty. Operand 225 states and 403 transitions. [2018-06-22 02:31:56,589 INFO ]: Finished isEmpty. Found accepting run of length 28 [2018-06-22 02:31:56,589 INFO ]: Found error trace [2018-06-22 02:31:56,589 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:31:56,589 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:31:56,589 INFO ]: Analyzing trace with hash 1863957242, now seen corresponding path program 1 times [2018-06-22 02:31:56,589 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:31:56,589 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:31:56,590 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:56,590 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:31:56,590 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:31:56,614 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:31:56,965 INFO ]: Checked inductivity of 11 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 02:31:56,965 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 02:31:56,965 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 02:31:56,979 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:31:57,000 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:31:57,008 INFO ]: Computing forward predicates... [2018-06-22 02:31:57,154 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 02:31:57,393 INFO ]: Checked inductivity of 11 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 02:31:57,415 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 02:31:57,415 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 13 [2018-06-22 02:31:57,416 INFO ]: Interpolant automaton has 13 states [2018-06-22 02:31:57,416 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 02:31:57,416 INFO ]: CoverageRelationStatistics Valid=24, Invalid=132, Unknown=0, NotChecked=0, Total=156 [2018-06-22 02:31:57,416 INFO ]: Start difference. First operand 225 states and 403 transitions. Second operand 13 states. [2018-06-22 02:31:58,142 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 32 [2018-06-22 02:31:58,440 WARN ]: Spent 209.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 20 [2018-06-22 02:32:04,041 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:32:04,041 INFO ]: Finished difference Result 1134 states and 5474 transitions. [2018-06-22 02:32:04,042 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-22 02:32:04,042 INFO ]: Start accepts. Automaton has 13 states. Word has length 27 [2018-06-22 02:32:04,042 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:32:04,205 INFO ]: With dead ends: 1134 [2018-06-22 02:32:04,205 INFO ]: Without dead ends: 978 [2018-06-22 02:32:04,206 INFO ]: 0 DeclaredPredicates, 45 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=91, Invalid=461, Unknown=0, NotChecked=0, Total=552 [2018-06-22 02:32:04,207 INFO ]: Start minimizeSevpa. Operand 978 states. [2018-06-22 02:32:04,530 INFO ]: Finished minimizeSevpa. Reduced states from 978 to 279. [2018-06-22 02:32:04,530 INFO ]: Start removeUnreachable. Operand 279 states. [2018-06-22 02:32:04,541 INFO ]: Finished removeUnreachable. Reduced from 279 states to 279 states and 532 transitions. [2018-06-22 02:32:04,541 INFO ]: Start accepts. Automaton has 279 states and 532 transitions. Word has length 27 [2018-06-22 02:32:04,541 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:32:04,541 INFO ]: Abstraction has 279 states and 532 transitions. [2018-06-22 02:32:04,541 INFO ]: Interpolant automaton has 13 states. [2018-06-22 02:32:04,541 INFO ]: Start isEmpty. Operand 279 states and 532 transitions. [2018-06-22 02:32:04,566 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-22 02:32:04,566 INFO ]: Found error trace [2018-06-22 02:32:04,567 INFO ]: trace histogram [4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:32:04,567 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:32:04,567 INFO ]: Analyzing trace with hash 1662854507, now seen corresponding path program 1 times [2018-06-22 02:32:04,567 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:32:04,567 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:32:04,568 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:32:04,568 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:32:04,568 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:32:04,609 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:32:04,851 INFO ]: Checked inductivity of 43 backedges. 10 proven. 11 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-22 02:32:04,851 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 02:32:04,851 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) [2018-06-22 02:32:04,868 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 02:32:04,900 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:32:04,903 INFO ]: Computing forward predicates... [2018-06-22 02:32:04,975 INFO ]: Checked inductivity of 43 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2018-06-22 02:32:05,007 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 02:32:05,007 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [12] total 15 [2018-06-22 02:32:05,007 INFO ]: Interpolant automaton has 15 states [2018-06-22 02:32:05,008 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 02:32:05,008 INFO ]: CoverageRelationStatistics Valid=30, Invalid=180, Unknown=0, NotChecked=0, Total=210 [2018-06-22 02:32:05,008 INFO ]: Start difference. First operand 279 states and 532 transitions. Second operand 15 states. [2018-06-22 02:32:09,842 WARN ]: Spent 169.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 02:32:34,617 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:32:34,617 INFO ]: Finished difference Result 2893 states and 28224 transitions. [2018-06-22 02:32:34,617 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 108 states. [2018-06-22 02:32:34,617 INFO ]: Start accepts. Automaton has 15 states. Word has length 46 [2018-06-22 02:32:34,617 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:32:35,253 INFO ]: With dead ends: 2893 [2018-06-22 02:32:35,253 INFO ]: Without dead ends: 2328 [2018-06-22 02:32:35,258 INFO ]: 0 DeclaredPredicates, 204 GetRequests, 92 SyntacticMatches, 0 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4865 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=1363, Invalid=11519, Unknown=0, NotChecked=0, Total=12882 [2018-06-22 02:32:35,259 INFO ]: Start minimizeSevpa. Operand 2328 states. [2018-06-22 02:32:36,824 INFO ]: Finished minimizeSevpa. Reduced states from 2328 to 734. [2018-06-22 02:32:36,825 INFO ]: Start removeUnreachable. Operand 734 states. [2018-06-22 02:32:36,875 INFO ]: Finished removeUnreachable. Reduced from 734 states to 734 states and 2353 transitions. [2018-06-22 02:32:36,876 INFO ]: Start accepts. Automaton has 734 states and 2353 transitions. Word has length 46 [2018-06-22 02:32:36,876 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:32:36,876 INFO ]: Abstraction has 734 states and 2353 transitions. [2018-06-22 02:32:36,876 INFO ]: Interpolant automaton has 15 states. [2018-06-22 02:32:36,876 INFO ]: Start isEmpty. Operand 734 states and 2353 transitions. [2018-06-22 02:32:36,952 INFO ]: Finished isEmpty. Found accepting run of length 51 [2018-06-22 02:32:36,952 INFO ]: Found error trace [2018-06-22 02:32:36,952 INFO ]: trace histogram [4, 4, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:32:36,952 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:32:36,954 INFO ]: Analyzing trace with hash -486114561, now seen corresponding path program 1 times [2018-06-22 02:32:36,954 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:32:36,954 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:32:36,955 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:32:36,955 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:32:36,955 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:32:36,981 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:32:37,145 INFO ]: Checked inductivity of 56 backedges. 23 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2018-06-22 02:32:37,145 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 02:32:37,145 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) [2018-06-22 02:32:37,155 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 02:32:37,197 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:32:37,200 INFO ]: Computing forward predicates... [2018-06-22 02:32:37,553 INFO ]: Checked inductivity of 56 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-06-22 02:32:37,583 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 02:32:37,583 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [4] total 7 [2018-06-22 02:32:37,583 INFO ]: Interpolant automaton has 7 states [2018-06-22 02:32:37,583 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 02:32:37,584 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 02:32:37,584 INFO ]: Start difference. First operand 734 states and 2353 transitions. Second operand 7 states. [2018-06-22 02:32:38,330 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 02:32:38,330 INFO ]: Finished difference Result 1624 states and 8218 transitions. [2018-06-22 02:32:38,331 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 02:32:38,331 INFO ]: Start accepts. Automaton has 7 states. Word has length 50 [2018-06-22 02:32:38,331 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 02:32:38,443 INFO ]: With dead ends: 1624 [2018-06-22 02:32:38,443 INFO ]: Without dead ends: 1088 [2018-06-22 02:32:38,443 INFO ]: 0 DeclaredPredicates, 65 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=47, Invalid=109, Unknown=0, NotChecked=0, Total=156 [2018-06-22 02:32:38,444 INFO ]: Start minimizeSevpa. Operand 1088 states. [2018-06-22 02:32:38,746 INFO ]: Finished minimizeSevpa. Reduced states from 1088 to 790. [2018-06-22 02:32:38,746 INFO ]: Start removeUnreachable. Operand 790 states. [2018-06-22 02:32:38,778 INFO ]: Finished removeUnreachable. Reduced from 790 states to 790 states and 2481 transitions. [2018-06-22 02:32:38,778 INFO ]: Start accepts. Automaton has 790 states and 2481 transitions. Word has length 50 [2018-06-22 02:32:38,778 INFO ]: Finished accepts. word is rejected. [2018-06-22 02:32:38,778 INFO ]: Abstraction has 790 states and 2481 transitions. [2018-06-22 02:32:38,778 INFO ]: Interpolant automaton has 7 states. [2018-06-22 02:32:38,778 INFO ]: Start isEmpty. Operand 790 states and 2481 transitions. [2018-06-22 02:32:38,836 INFO ]: Finished isEmpty. Found accepting run of length 52 [2018-06-22 02:32:38,836 INFO ]: Found error trace [2018-06-22 02:32:38,836 INFO ]: trace histogram [4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 02:32:38,836 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 02:32:38,837 INFO ]: Analyzing trace with hash 1866412169, now seen corresponding path program 1 times [2018-06-22 02:32:38,837 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 02:32:38,837 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 02:32:38,837 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:32:38,837 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 02:32:38,837 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 02:32:38,869 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:32:39,994 INFO ]: Checked inductivity of 63 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-06-22 02:32:39,994 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 02:32:39,994 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) [2018-06-22 02:32:40,009 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 02:32:40,048 INFO ]: Conjunction of SSA is unsat [2018-06-22 02:32:40,054 INFO ]: Computing forward predicates... [2018-06-22 02:32:40,353 INFO ]: Checked inductivity of 63 backedges. 14 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-22 02:32:40,382 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 02:32:40,382 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 19 [2018-06-22 02:32:40,382 INFO ]: Interpolant automaton has 19 states [2018-06-22 02:32:40,383 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 02:32:40,383 INFO ]: CoverageRelationStatistics Valid=43, Invalid=299, Unknown=0, NotChecked=0, Total=342 [2018-06-22 02:32:40,383 INFO ]: Start difference. First operand 790 states and 2481 transitions. Second operand 19 states. Received shutdown request... [2018-06-22 02:32:56,192 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 91 states. [2018-06-22 02:32:56,192 WARN ]: Verification canceled [2018-06-22 02:32:56,199 WARN ]: Timeout [2018-06-22 02:32:56,199 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:32:56 BoogieIcfgContainer [2018-06-22 02:32:56,199 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 02:32:56,200 INFO ]: Toolchain (without parser) took 64371.86 ms. Allocated memory was 308.8 MB in the beginning and 1.1 GB in the end (delta: 749.2 MB). Free memory was 263.2 MB in the beginning and 357.6 MB in the end (delta: -94.5 MB). Peak memory consumption was 654.7 MB. Max. memory is 3.6 GB. [2018-06-22 02:32:56,204 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 02:32:56,204 INFO ]: ChcToBoogie took 62.97 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 259.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 02:32:56,204 INFO ]: Boogie Preprocessor took 58.15 ms. Allocated memory is still 308.8 MB. Free memory is still 259.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 02:32:56,205 INFO ]: RCFGBuilder took 707.25 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 241.2 MB in the end (delta: 18.0 MB). Peak memory consumption was 18.0 MB. Max. memory is 3.6 GB. [2018-06-22 02:32:56,205 INFO ]: TraceAbstraction took 63534.34 ms. Allocated memory was 308.8 MB in the beginning and 1.1 GB in the end (delta: 749.2 MB). Free memory was 241.2 MB in the beginning and 357.6 MB in the end (delta: -116.4 MB). Peak memory consumption was 632.8 MB. Max. memory is 3.6 GB. [2018-06-22 02:32:56,211 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 62.97 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 259.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 58.15 ms. Allocated memory is still 308.8 MB. Free memory is still 259.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 707.25 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 241.2 MB in the end (delta: 18.0 MB). Peak memory consumption was 18.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63534.34 ms. Allocated memory was 308.8 MB in the beginning and 1.1 GB in the end (delta: 749.2 MB). Free memory was 241.2 MB in the beginning and 357.6 MB in the end (delta: -116.4 MB). Peak memory consumption was 632.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 (790states) and interpolant automaton (currently 91 states, 19 states before enhancement), while ReachableStatesComputation was computing reachable states (3150 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 52 locations, 1 error locations. TIMEOUT Result, 63.4s OverallTime, 10 OverallIterations, 4 TraceHistogramMax, 56.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1635 SDtfs, 3083 SDslu, 7318 SDs, 0 SdLazy, 56380 SolverSat, 6726 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 43.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 523 GetRequests, 266 SyntacticMatches, 0 SemanticMatches, 257 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8366 ImplicationChecksByTransitivity, 6.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=790occurred in iteration=9, 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: 2.4s AutomataMinimizationTime, 9 MinimizatonAttempts, 2591 StatesRemovedByMinimization, 3 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 3.4s InterpolantComputationTime, 407 NumberOfCodeBlocks, 407 NumberOfCodeBlocksAsserted, 14 NumberOfCheckSat, 393 ConstructedInterpolants, 0 QuantifiedInterpolants, 34159 SizeOfPredicates, 24 NumberOfNonLiveVariables, 678 ConjunctsInSsa, 58 ConjunctsInUnsatCore, 14 InterpolantComputations, 8 PerfectInterpolantSequences, 308/346 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/rec__mccarthy91.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_02-32-56-227.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/rec__mccarthy91.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_02-32-56-227.csv Completed graceful shutdown