java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/down.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:21:20,524 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:21:20,527 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:21:20,542 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:21:20,543 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:21:20,543 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:21:20,545 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:21:20,546 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:21:20,548 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:21:20,549 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:21:20,550 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:21:20,550 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:21:20,551 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:21:20,552 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:21:20,552 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:21:20,553 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:21:20,558 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:21:20,560 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:21:20,563 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:21:20,564 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:21:20,565 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:21:20,567 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:21:20,567 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:21:20,568 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:21:20,569 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:21:20,570 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:21:20,570 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:21:20,571 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:21:20,572 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:21:20,572 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:21:20,573 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:21:20,573 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:21:20,574 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:21:20,574 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:21:20,575 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:21:20,575 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:21:20,589 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:21:20,589 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:21:20,589 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:21:20,590 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:21:20,591 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:21:20,591 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:21:20,591 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:21:20,591 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:21:20,591 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:21:20,592 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:21:20,592 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:21:20,592 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:21:20,592 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:21:20,592 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:21:20,592 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:21:20,593 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:21:20,593 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:21:20,594 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:21:20,594 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:21:20,642 INFO ]: Repository-Root is: /tmp [2018-06-22 05:21:20,661 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:21:20,666 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:21:20,668 INFO ]: Initializing SmtParser... [2018-06-22 05:21:20,668 INFO ]: SmtParser initialized [2018-06-22 05:21:20,669 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/down.c.smt2 [2018-06-22 05:21:20,670 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 05:21:20,857 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/down.c.smt2 unknown [2018-06-22 05:21:21,097 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/down.c.smt2 [2018-06-22 05:21:21,101 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:21:21,108 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:21:21,108 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:21:21,108 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:21:21,108 INFO ]: ChcToBoogie initialized [2018-06-22 05:21:21,112 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:21:21" (1/1) ... [2018-06-22 05:21:21,170 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21 Unit [2018-06-22 05:21:21,170 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:21:21,171 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:21:21,171 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:21:21,171 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:21:21,192 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (1/1) ... [2018-06-22 05:21:21,193 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (1/1) ... [2018-06-22 05:21:21,200 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (1/1) ... [2018-06-22 05:21:21,202 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (1/1) ... [2018-06-22 05:21:21,206 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (1/1) ... [2018-06-22 05:21:21,214 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (1/1) ... [2018-06-22 05:21:21,215 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (1/1) ... [2018-06-22 05:21:21,224 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:21:21,225 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:21:21,225 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:21:21,225 INFO ]: RCFGBuilder initialized [2018-06-22 05:21:21,226 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 05:21:21,238 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:21:21,238 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:21:21,238 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:21:21,239 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:21:21,239 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:21:21,239 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:21:21,598 INFO ]: Using library mode [2018-06-22 05:21:21,599 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:21:21 BoogieIcfgContainer [2018-06-22 05:21:21,599 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:21:21,600 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:21:21,600 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:21:21,603 INFO ]: TraceAbstraction initialized [2018-06-22 05:21:21,604 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:21:21" (1/3) ... [2018-06-22 05:21:21,605 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6fbfef6d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:21:21, skipping insertion in model container [2018-06-22 05:21:21,605 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:21:21" (2/3) ... [2018-06-22 05:21:21,605 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6fbfef6d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:21:21, skipping insertion in model container [2018-06-22 05:21:21,605 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:21:21" (3/3) ... [2018-06-22 05:21:21,607 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:21:21,631 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:21:21,640 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:21:21,691 INFO ]: Using default assertion order modulation [2018-06-22 05:21:21,692 INFO ]: Interprodecural is true [2018-06-22 05:21:21,692 INFO ]: Hoare is false [2018-06-22 05:21:21,692 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:21:21,692 INFO ]: Backedges is TWOTRACK [2018-06-22 05:21:21,692 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:21:21,692 INFO ]: Difference is false [2018-06-22 05:21:21,692 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:21:21,692 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:21:21,705 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:21:21,714 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:21:21,714 INFO ]: Found error trace [2018-06-22 05:21:21,715 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:21,715 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:21,722 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 05:21:21,723 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:21,724 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:21,767 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:21,767 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:21:21,767 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:21,811 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:21,878 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:21,880 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:21:21,880 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:21:21,881 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:21:21,891 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:21:21,892 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:21:21,894 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:21:21,951 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:21:21,951 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:21:21,952 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:21:21,953 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:21:21,954 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:21:21,962 INFO ]: With dead ends: 9 [2018-06-22 05:21:21,962 INFO ]: Without dead ends: 9 [2018-06-22 05:21:21,965 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:21:21,977 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:21:21,992 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:21:21,997 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:21:21,998 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:21:21,998 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:21:21,999 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:21:21,999 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:21:21,999 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:21:21,999 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:21:21,999 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:21:21,999 INFO ]: Found error trace [2018-06-22 05:21:21,999 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:21,999 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:21,999 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 05:21:21,999 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:21,999 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:22,000 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:22,000 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:21:22,000 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:22,026 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:22,125 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:22,125 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:21:22,125 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:21:22,134 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:21:22,173 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:22,184 INFO ]: Computing forward predicates... [2018-06-22 05:21:22,290 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:22,312 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:21:22,312 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 05:21:22,312 INFO ]: Interpolant automaton has 5 states [2018-06-22 05:21:22,313 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 05:21:22,313 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:21:22,313 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 05:21:22,429 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:21:22,429 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 05:21:22,432 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 05:21:22,432 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 05:21:22,432 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:21:22,433 INFO ]: With dead ends: 10 [2018-06-22 05:21:22,433 INFO ]: Without dead ends: 10 [2018-06-22 05:21:22,434 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:21:22,434 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 05:21:22,435 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 05:21:22,435 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 05:21:22,435 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 05:21:22,435 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 05:21:22,436 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:21:22,436 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 05:21:22,436 INFO ]: Interpolant automaton has 5 states. [2018-06-22 05:21:22,436 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 05:21:22,436 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 05:21:22,436 INFO ]: Found error trace [2018-06-22 05:21:22,436 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:22,436 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:22,436 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-22 05:21:22,436 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:22,436 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:22,437 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:22,437 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:21:22,437 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:22,473 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:22,748 WARN ]: Spent 122.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 05:21:22,749 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:22,749 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:21:22,749 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 05:21:22,765 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:21:22,826 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:21:22,826 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:22,828 INFO ]: Computing forward predicates... [2018-06-22 05:21:23,638 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:23,658 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:21:23,658 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-22 05:21:23,658 INFO ]: Interpolant automaton has 6 states [2018-06-22 05:21:23,658 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 05:21:23,658 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:21:23,658 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-22 05:21:23,696 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:21:23,696 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 05:21:23,697 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 05:21:23,697 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-22 05:21:23,697 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:21:23,697 INFO ]: With dead ends: 11 [2018-06-22 05:21:23,697 INFO ]: Without dead ends: 11 [2018-06-22 05:21:23,698 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:21:23,698 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 05:21:23,699 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 05:21:23,699 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 05:21:23,699 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 05:21:23,699 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-22 05:21:23,699 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:21:23,699 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 05:21:23,699 INFO ]: Interpolant automaton has 6 states. [2018-06-22 05:21:23,699 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 05:21:23,700 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 05:21:23,700 INFO ]: Found error trace [2018-06-22 05:21:23,700 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:23,700 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:23,700 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 3 times [2018-06-22 05:21:23,700 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:23,700 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:23,701 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:23,701 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:21:23,701 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:23,740 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:23,966 WARN ]: Spent 153.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 05:21:24,022 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:24,022 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:21:24,023 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:21:24,029 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:21:24,108 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 05:21:24,108 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:24,111 INFO ]: Computing forward predicates... [2018-06-22 05:21:25,286 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:25,312 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:21:25,312 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-22 05:21:25,312 INFO ]: Interpolant automaton has 7 states [2018-06-22 05:21:25,312 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 05:21:25,313 INFO ]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2018-06-22 05:21:25,313 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-22 05:21:25,419 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:21:25,419 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 05:21:25,420 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 05:21:25,420 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-22 05:21:25,420 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:21:25,420 INFO ]: With dead ends: 13 [2018-06-22 05:21:25,420 INFO ]: Without dead ends: 13 [2018-06-22 05:21:25,421 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=37, Invalid=53, Unknown=0, NotChecked=0, Total=90 [2018-06-22 05:21:25,421 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 05:21:25,422 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 05:21:25,422 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 05:21:25,423 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 05:21:25,423 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 10 [2018-06-22 05:21:25,423 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:21:25,423 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 05:21:25,423 INFO ]: Interpolant automaton has 7 states. [2018-06-22 05:21:25,423 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 05:21:25,424 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 05:21:25,424 INFO ]: Found error trace [2018-06-22 05:21:25,424 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:25,424 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:25,424 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 4 times [2018-06-22 05:21:25,424 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:25,424 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:25,425 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:25,425 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:21:25,425 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:25,524 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:25,820 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:25,820 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:21:25,821 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:21:25,826 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 05:21:25,879 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 05:21:25,879 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:25,883 INFO ]: Computing forward predicates... [2018-06-22 05:21:30,160 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:21:32,255 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:32,288 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:21:32,288 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-22 05:21:32,288 INFO ]: Interpolant automaton has 10 states [2018-06-22 05:21:32,288 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 05:21:32,288 INFO ]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2018-06-22 05:21:32,288 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 10 states. [2018-06-22 05:21:32,868 WARN ]: Spent 473.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 10 [2018-06-22 05:21:33,209 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:21:33,209 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 05:21:33,209 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 05:21:33,209 INFO ]: Start accepts. Automaton has 10 states. Word has length 12 [2018-06-22 05:21:33,209 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:21:33,209 INFO ]: With dead ends: 14 [2018-06-22 05:21:33,209 INFO ]: Without dead ends: 14 [2018-06-22 05:21:33,210 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=79, Invalid=161, Unknown=0, NotChecked=0, Total=240 [2018-06-22 05:21:33,210 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 05:21:33,211 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 05:21:33,211 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 05:21:33,212 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 05:21:33,212 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-22 05:21:33,212 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:21:33,212 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 05:21:33,212 INFO ]: Interpolant automaton has 10 states. [2018-06-22 05:21:33,212 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 05:21:33,212 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 05:21:33,212 INFO ]: Found error trace [2018-06-22 05:21:33,212 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:33,212 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:33,213 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 5 times [2018-06-22 05:21:33,213 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:33,213 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:33,213 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:33,213 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:21:33,213 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:33,295 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:33,922 WARN ]: Spent 302.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 05:21:34,018 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:34,018 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:21:34,018 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:21:34,024 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 05:21:34,060 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 05:21:34,060 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:34,063 INFO ]: Computing forward predicates... [2018-06-22 05:21:40,492 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:40,511 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:21:40,535 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 11 [2018-06-22 05:21:40,535 INFO ]: Interpolant automaton has 11 states [2018-06-22 05:21:40,535 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 05:21:40,535 INFO ]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-06-22 05:21:40,535 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 11 states. [2018-06-22 05:21:40,803 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 25 [2018-06-22 05:21:40,952 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:21:40,952 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-22 05:21:40,952 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 05:21:40,952 INFO ]: Start accepts. Automaton has 11 states. Word has length 13 [2018-06-22 05:21:40,953 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:21:40,953 INFO ]: With dead ends: 15 [2018-06-22 05:21:40,953 INFO ]: Without dead ends: 15 [2018-06-22 05:21:40,953 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 5 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=107, Invalid=199, Unknown=0, NotChecked=0, Total=306 [2018-06-22 05:21:40,954 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 05:21:40,955 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 05:21:40,955 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 05:21:40,955 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-22 05:21:40,956 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-22 05:21:40,956 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:21:40,956 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-22 05:21:40,956 INFO ]: Interpolant automaton has 11 states. [2018-06-22 05:21:40,956 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-22 05:21:40,956 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 05:21:40,956 INFO ]: Found error trace [2018-06-22 05:21:40,956 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:40,956 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:40,956 INFO ]: Analyzing trace with hash -414382217, now seen corresponding path program 6 times [2018-06-22 05:21:40,956 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:40,956 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:40,957 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:40,957 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:21:40,957 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:41,055 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:41,654 WARN ]: Spent 356.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 05:21:41,759 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:41,760 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:21:41,760 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:21:41,789 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 05:21:41,841 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-22 05:21:41,841 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:41,846 INFO ]: Computing forward predicates... [2018-06-22 05:21:45,552 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:45,578 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:21:45,608 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-22 05:21:45,608 INFO ]: Interpolant automaton has 15 states [2018-06-22 05:21:45,608 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 05:21:45,608 INFO ]: CoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2018-06-22 05:21:45,608 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 15 states. [2018-06-22 05:21:45,969 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:21:45,969 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-22 05:21:45,969 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 05:21:45,969 INFO ]: Start accepts. Automaton has 15 states. Word has length 14 [2018-06-22 05:21:45,969 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:21:45,969 INFO ]: With dead ends: 16 [2018-06-22 05:21:45,969 INFO ]: Without dead ends: 16 [2018-06-22 05:21:45,970 INFO ]: 0 DeclaredPredicates, 31 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 106 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=161, Invalid=345, Unknown=0, NotChecked=0, Total=506 [2018-06-22 05:21:45,970 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-22 05:21:45,972 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-22 05:21:45,972 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-22 05:21:45,972 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-22 05:21:45,972 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-06-22 05:21:45,972 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:21:45,972 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-22 05:21:45,973 INFO ]: Interpolant automaton has 15 states. [2018-06-22 05:21:45,973 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-22 05:21:45,973 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-22 05:21:45,973 INFO ]: Found error trace [2018-06-22 05:21:45,973 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:45,973 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:45,973 INFO ]: Analyzing trace with hash 39881678, now seen corresponding path program 7 times [2018-06-22 05:21:45,973 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:45,973 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:45,974 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:45,974 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:21:45,974 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:46,048 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:46,295 WARN ]: Spent 106.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 05:21:46,478 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:46,478 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:21:46,478 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:21:46,487 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:21:46,537 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:46,542 INFO ]: Computing forward predicates... [2018-06-22 05:21:51,084 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:21:51,781 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:51,801 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:21:51,801 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 13 [2018-06-22 05:21:51,802 INFO ]: Interpolant automaton has 13 states [2018-06-22 05:21:51,802 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 05:21:51,802 INFO ]: CoverageRelationStatistics Valid=50, Invalid=106, Unknown=0, NotChecked=0, Total=156 [2018-06-22 05:21:51,802 INFO ]: Start difference. First operand 16 states and 16 transitions. Second operand 13 states. [2018-06-22 05:21:52,093 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 25 [2018-06-22 05:21:52,281 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:21:52,281 INFO ]: Finished difference Result 17 states and 17 transitions. [2018-06-22 05:21:52,281 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 05:21:52,281 INFO ]: Start accepts. Automaton has 13 states. Word has length 15 [2018-06-22 05:21:52,281 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:21:52,282 INFO ]: With dead ends: 17 [2018-06-22 05:21:52,282 INFO ]: Without dead ends: 17 [2018-06-22 05:21:52,282 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 7 SyntacticMatches, 7 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=175, Invalid=287, Unknown=0, NotChecked=0, Total=462 [2018-06-22 05:21:52,282 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 05:21:52,283 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 05:21:52,283 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 05:21:52,284 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-06-22 05:21:52,284 INFO ]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 15 [2018-06-22 05:21:52,284 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:21:52,284 INFO ]: Abstraction has 17 states and 17 transitions. [2018-06-22 05:21:52,284 INFO ]: Interpolant automaton has 13 states. [2018-06-22 05:21:52,284 INFO ]: Start isEmpty. Operand 17 states and 17 transitions. [2018-06-22 05:21:52,284 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 05:21:52,284 INFO ]: Found error trace [2018-06-22 05:21:52,284 INFO ]: trace histogram [9, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:21:52,284 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:21:52,284 INFO ]: Analyzing trace with hash 1237160535, now seen corresponding path program 8 times [2018-06-22 05:21:52,284 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:21:52,284 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:21:52,285 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:52,285 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:21:52,285 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:21:52,410 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:52,686 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 16 [2018-06-22 05:21:53,211 WARN ]: Spent 240.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 21 [2018-06-22 05:21:53,388 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:21:53,388 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:21:53,388 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:21:53,403 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:21:53,456 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:21:53,456 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:21:53,460 INFO ]: Computing forward predicates... [2018-06-22 05:22:06,559 WARN ]: expecting exponential blowup for input size 7 Received shutdown request... [2018-06-22 05:22:25,816 INFO ]: Timeout while computing interpolants [2018-06-22 05:22:26,017 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:22:26,017 WARN ]: Verification canceled [2018-06-22 05:22:26,022 WARN ]: Timeout [2018-06-22 05:22:26,022 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:22:26 BoogieIcfgContainer [2018-06-22 05:22:26,022 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:22:26,022 INFO ]: Toolchain (without parser) took 64920.58 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 257.0 MB in the beginning and 268.6 MB in the end (delta: -11.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:22:26,023 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 304.6 MB. Free memory is still 267.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 05:22:26,024 INFO ]: ChcToBoogie took 62.20 ms. Allocated memory is still 304.6 MB. Free memory was 255.0 MB in the beginning and 253.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:22:26,024 INFO ]: Boogie Preprocessor took 53.34 ms. Allocated memory is still 304.6 MB. Free memory is still 253.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 05:22:26,024 INFO ]: RCFGBuilder took 374.34 ms. Allocated memory is still 304.6 MB. Free memory was 253.0 MB in the beginning and 243.0 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:22:26,025 INFO ]: TraceAbstraction took 64421.52 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 243.0 MB in the beginning and 268.6 MB in the end (delta: -25.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:22:26,027 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 304.6 MB. Free memory is still 267.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 62.20 ms. Allocated memory is still 304.6 MB. Free memory was 255.0 MB in the beginning and 253.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 53.34 ms. Allocated memory is still 304.6 MB. Free memory is still 253.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 374.34 ms. Allocated memory is still 304.6 MB. Free memory was 253.0 MB in the beginning and 243.0 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64421.52 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 243.0 MB in the beginning and 268.6 MB in the end (delta: -25.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 17 with TraceHistMax 9, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 13768 quantified variables from 13 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 64.3s OverallTime, 9 OverallIterations, 9 TraceHistogramMax, 2.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 21 SDslu, 178 SDs, 0 SdLazy, 72 SolverSat, 51 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 166 GetRequests, 52 SyntacticMatches, 24 SemanticMatches, 90 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 325 ImplicationChecksByTransitivity, 5.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=17occurred in iteration=8, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 26.7s InterpolantComputationTime, 169 NumberOfCodeBlocks, 169 NumberOfCodeBlocksAsserted, 25 NumberOfCheckSat, 154 ConstructedInterpolants, 0 QuantifiedInterpolants, 10562 SizeOfPredicates, 28 NumberOfNonLiveVariables, 1261 ConjunctsInSsa, 274 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/220 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/down.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-22-26-038.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/down.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-22-26-038.csv Completed graceful shutdown