Design and Organization

This document contains information about the:

• Changes
• Divisions
  • Competition Divisions
  • Demonstration Division
• Infrastructure
  • Computers
  • Problems
  • Resource Limits
• System Evaluation
• System Entry
  • System Description
  • Sample Solutions
• System Requirements
  • System Properties
  • System Delivery
  • System Execution
  • System Checks

Disclaimer

• CNF problems are used in only the EPR division (because CNF is now the assembly language of ATP).

• The FOF, FNT, and LTB divisions no longer have an assurance ranking class. They have only proof/model ranking classes.

• The LTB division's problem categories are accompanied by sets of training problems and their solutions (taken from the same exports as the competition problems), that can be used for tuning and training during (typically at the start of) the competition.

• There have been some minor changes to the Batch Specification Files.

• Systems are expected to use the SZS ontology and standards for reporting their results.

• Systems are expected to use the proposed TPTP ATP System Building Conventions for their installation.

• Execution is now monitored by Oliver Roussel's RunSolver, with consequent changes to the System Checks.

Competition Divisions

• The THF division: Typed Higher-order Form theorems (axioms with a provable conjecture), using the THF0 syntax. The THF division has two problem categories:
  • The TNE category: THF with No Equality
  • The TEQ category: THF with EQuality

• The TFA division: Typed First-order with Arithmetic theorems (axioms with a provable conjecture), using the TFF0 syntax. The TFA division has two problem categories:
  • The TFI category: TFA with only Integer arithmetic
  • The TFR category: TFA with only Rational or only Real arithmetic (no mixed rational and real arithmetic)

• The FOF division: First-Order Form syntactically non-propositional theorems (axioms with a provable conjecture). The FOF division has two problem categories:
  • The FNE category: FOF with No Equality
  • The FEQ category: FOF with EQuality

• The FNT division: First-order form syntactically non-propositional Non-Theorems (axioms with a countersatisfiable conjecture, and satisfiable axiom sets). The FNT division has two problem categories:
  • The FNN category: FNT with No equality
  • The FNQ category: FNT with eQuality

• The EPR division: Effectively PRopositional clause normal form theorems and non-theorems (clause sets). The EPR division has two problem categories:
  • The EPT category: Effectively Propositional Theorems (unsatisfiable clause sets)
  • The EPS category: Effectively Propositional non-theorems (Satisfiable clause sets)

• The LTB division: First-order form non-propositional theorems (axioms with a provable conjecture) from Large Theories, presented in Batches. The LTB division's problem categories are accompanied by sets of training problems and their solutions, taken from the same exports as the competition problems, that can be used for tuning and training during (typically at the start of) the competition. The LTB division has three problem categories:
  • The HOL category: Problems exported from HOL Light.
  • The ISA category: Problems exported from Isabelle.
  • The MZR category: Problems exported from Mizar.

Demonstration Division

Computers

• Four (one quad core chip) Intel(R) Xeon(R) L5410, 2.333GHz CPUs
• 12GB memory
• The Linux 2.6.29.4-167.fc11.x86_64 operating system

Problems

The problems have to meet certain criteria to be eligible for selection:

• The TPTP uses system performance data to compute problem difficulty ratings, and from the ratings classifies problems as one of:
  • Easy: Solvable by all state-of-the-art ATP systems
  • Difficult: Solvable by some state-of-the-art ATP systems
  • Unsolved: Not yet solved by any ATP system
  • Open: Theorem-hood unknown
  Difficult problems with a rating in the range 0.21 to 0.99 are eligible. Problems of lesser and greater ratings might also be eligible in some divisions (especially the batch divisions, because the TPTP problem ratings are computed from non-batch mode results). Performance data from systems submitted by the system submission deadline is used for computing the problem ratings for the TPTP version used for the competition.
• The TPTP distinguishes versions of problems as one of standard, incomplete, augmented, especial, or biased. All except biased problems are eligible.
• In the LTB division there is consistent symbol usage and formula naming between the training problems and the competition problems.

• The selection is constrained so that no division or category contains an excessive number of very similar problems.
• The selection mechanism is biased to select problems that are new in the TPTP version used, until 50% of the problems in each category have been selected, after which random selection (from old and new problems) continues. The actual percentage of new problems used depends on how many new problems are eligible and the limitation on very similar problems.

Number of Problems
The minimal numbers of problems that must be used in each division and category, to ensure sufficient confidence in the competition results, are determined from the numbers of eligible problems in each division and category (the competition organizers have to ensure that there are sufficient computers available to run the ATP systems on this minimal number of problems). The minimal numbers of problems are used in determining the time limits imposed on each solution attempt.

A lower bound on the total number of problems to be used is determined from the number of computers available, the time allocated to the competition, the number of ATP systems to be run on the competition computers over all the divisions, and the time limit per problem, according to the following relationship:

                   NumberOfComputers * TimeAllocated
NumberOfProblems = ---------------------------------
                     NumberOfATPSystems * TimeLimit

The numbers of problems used in each division and problem category are (roughly) proportional to the numbers of eligible problems, after taking into account the limitation on very similar problems. The numbers of problems used in each division and category are determined according to the judgement of the competition organizers.

Problem Preparation
The problems are in TPTP format, with include directives (included files are found relative to the TPTP environment variable). The problems in each non-batch division are given in increasing order of TPTP difficulty rating. The problems in each batch of batch divisions are given in the natural order of their export.

In order to ensure that no system receives an advantage or disadvantage due to the specific presentation of the problems in the TPTP, the problems are preprocessed to:

• strip out all comment lines, including the problem header
• randomly reorder the formulae/clauses (include directives are left before formulae, type declarations and definitions are kept before the symbols' uses)
• randomly swap the arguments of associative connectives, and randomly reverse implications
• randomly reverse equalities

Batch Specification Files
The problems in each problem category of batch divisions are listed in a batch specification file, containing global data lines and one or more batch specifications. The global data lines are:

• A problem category line of the form
      division.category division_mnemonic.category_mnemonic
  For the LTB division it will be
      division.category LTB.category_mnemonic
  where the category mnemonics are HOL, ISA, MZR.
• The name of a directory that contains training data in the form of problems in TPTP format and one or more solutions to each problem in TSTP format, in a line of the form
      division.category.training_directory directory_name
  A (toy) example directory is TrainingData.HOL. Note that the Axioms directory contains all the axiom files that can be used in the competition problems.

• A header line % SZS start BatchConfiguration
• A specification of whether or not the problems in the batch must be attempted in order is given, in a line of the form
      execution.order ordered/unordered
  For the LTB division it will be
      execution.order ordered
  i.e., systems may not start any attempt on a problem, including reading the problem file, before ending the attempt on the preceding problem.
• A specification of what output is required from the ATP systems for each problem, in a line of the form
      output.required space_separated_list
  where the available list values are the SZS values Assurance, Proof, Model, and Answer. For the LTB division it will be
      output.required Proof
• The wall clock time limit per problem, in a line of the form
      limit.time.problem.wc limit_in_seconds
  A value of zero indicates no per-problem limit.
• The overall wall clock time limit (for the batch) is given in a line of the form
      limit.time.overall.wc limit_in_seconds
• A terminator line % SZS end BatchConfiguration
• A header line % SZS start BatchIncludes
• include directives that are used in every problem. Problems in the batch have all these include directives, and can also have other include directives that are not listed here.
• A terminator line % SZS end BatchIncludes
• A header line % SZS start BatchProblems
• Pairs of absolute problem file names, and absolute output file names where the output for the problem must be written.
• A terminator line % SZS end BatchProblems

Resource Limits

In the demonstration division, each entrant can choose to use either a CPU or a wall clock time limit, whose value is the CPU time limit of the competition divisions.

LTB division
For each batch there is a wall clock time limit per problem, which is provided in the configuration section at the start of each batch. The minimal wall clock time limit per problem is 30s. For each problem category there is an overall wall clock time limit, which is provided in the configuration section at the start of each batch, and is also available as a command line parameter. The overall limit is the sum over the batches of the batch's per-problem limit multiplied by the number of problems in the batch. Time spent before starting the first problem of a batch (e.g., preloading and analysing the batch axioms), and times spent between ending a problem and starting the next (e.g., learning from a proof just found), are not part of the times taken on the individual problems, but are part of the overall time taken. There are no CPU time limits.

The systems are ranked in the competition divisions, from the performance data. The THF, TFA, and EPR divisions have an assurance ranking class, ranked according to the number of problems solved, but not necessarily accompanied by a proof or model (thus giving only an assurance of the existence of a proof/model). The FOF, FNT, and LTB divisions have a proof/model ranking class, ranked according to the number of problems solved with an acceptable proof/model output. Ties are broken according to the average time over problems solved (CPU time for the non-batch divisions, wall clock time for the batch divisions). In the competition divisions, class winners are announced and prizes are awarded.

The competition panel decides whether or not the systems' proofs and models are acceptable for the proof/model ranking classes. The criteria include:

• Derivations must be complete, starting at formulae from the problem, and ending at the conjecture (for axiomatic proofs) or a false formula (for proofs by contradiction, including CNF refutations).
• For proofs of FOF problems by CNF refutation, the conversion from FOF to CNF must be adequately documented.
• Derivations must show only relevant inference steps.
• Inference steps must document the parent formulae, the inference rule used, and the inferred formula.
• Inference steps must be reasonably fine-grained.
• An unsatisfiable set of ground instances of clauses is acceptable for establishing the unsatisfiability of a set of clauses.
• Models must be complete, documenting the domain, function maps, and predicate maps. The domain, function maps, and predicate maps may be specified by explicit ground lists (of mappings), or by any clear, terminating algorithm.

In addition to the ranking criteria, other measures are made and presented in the results:

• The state-of-the-art contribution (SOTAC) quantifies the unique abilities of each system. For each problem solved by a system, its SOTAC for the problem is the inverse of the number of systems that solved the problem. A system's overall SOTAC is its average SOTAC over the problems it solves.
• The efficiency measure balances the number of problems solved with the time taken. It is the average of the inverses of the times for problems solved (CPU times for the non-batch divisions, wall clock times for the LTB division, with times less than the timing granularity rounded up to the granularity, to avoid skewing caused by very low times) multiplied by the fraction of problems solved. This can be interpreted intuitively as the average of the solution rates for problems solved, multiplied by the fraction of problems solved.
• In divisions that use a wall clock time limit the core usage is the average of the ratios of CPU time to wall clock time used, over the problems solved. This measures the extent to which the systems take advantage the multiple cores.

At some time after the competition, all high ranking systems in the competition divisions are tested over the entire TPTP. This provides a final check for soundness (see the section on system properties regarding soundness checking before the competition). If a system is found to be unsound during or after the competition, but before the competition report is published, and it cannot be shown that the unsoundness did not manifest itself in the competition, then the system is retrospectively disqualified. At some time after the competition, the proofs and models from the winners of the proof/model ranking classes are checked by the panel. If any of the proofs or models are unacceptable, i.e., they are significantly worse than the samples provided, then that system is retrospectively disqualified. All disqualifications are explained in the competition report.

Systems can be entered at only the division level, and can be entered into more than one division (a system that is not entered into a competition division is assumed to perform worse than the entered systems, for that type of problem - wimping out is not an option). Entering many similar versions of the same system is deprecated, and entrants may be required to limit the number of system versions that they enter. Systems that rely essentially on running other ATP systems without adding value are deprecated; the competition panel may disallow or move such systems to the demonstration division. The division winners of the previous CASC are automatically entered into their divisions, to provide benchmarks against which progress can be judged.

System Description

• Architecture. This section introduces the ATP system, and describes the calculus and inference rules used.
• Strategies. This section describes the search strategies used, why they are effective, and how they are selected for given problems. Any strategy tuning that is based on specific problems' characteristics must be clearly described (and justified in light of the tuning restrictions).
• Implementation. This section describes the implementation of the ATP system, including the programming language used, important internal data structures, and any special code libraries used. The availability of the system is also given here.
• Expected competition performance. This section makes some predictions about the performance of the ATP system in each of the divisions and categories in which it is competing.
• References.

The system description has to be emailed to the competition organizers by the system description deadline. The system descriptions, along with information regarding the competition design and procedures, form the proceedings for the competition.

Sample Solutions

Proof samples for proof classes must include a proof for SEU140+2. Model samples for model classes must include models for NLP042+1 and SWV017+1. The sample solutions must illustrate the use of all inference rules. An explanation must be provided for any non-obvious features.

System Properties

Soundness and Completeness

1. Systems must be sound. At some time before the competition all the systems in the competition divisions are tested for soundness. Non-theorems are submitted to the systems in the THF, TFA, FOF, EPR, and LTB divisions, and theorems are submitted to the systems in the FNT and EPR divisions. Finding a proof of a non-theorem or a disproof of a theorem indicates unsoundness. If a system fails the soundness testing it must be repaired by the unsoundness repair deadline or be withdrawn. The soundness testing eliminates the possibility of a system simply delaying for some amount of time and then claiming to have found a solution. For systems running on computers supplied by the entrant in the demonstration division, the entrant must perform the soundness testing and report the results to the competition organizers.
2. Systems do not have to be complete in any sense, including calculus, search control, implementation, or resource requirements.
3. All techniques used must be general purpose, and expected to extend usefully to new unseen problems. The precomputation and storage of information about individual TPTP problems or their solutions is not allowed. Strategies and strategy selection based on individual TPTP problems or their solutions are not allowed. If machine learning procedures are used, the learning must ensure that sufficient generalization is obtained so that no there is no specialization to individual problems or their solutions.
   • The LTB division's problem categories are accompanied by sets of training problems and their solutions (taken from the same exports as the competition problems), that can be used for tuning and training during (typically at the start of) the competition. The training problems are not used in the competition. There are at least twice as many training problems as competition problems in each problem category. The training problems and solutions may be used for producing generally useful strategies that extend to "unseen" problems in the problem sets. Such strategies can rely on the consistent naming of symbols and formulas in the problem sets, and may use techniques for memorization and generalization of problems and solutions in the training set. The system description must fully explain any such tuning or training that has been done.

     For the LTB division problems will be taken from publicly available problem sets: the HOL problem category will use the HH7150 problem set; the ISA problem category will use the SH-CASC-14 problem set; the MZR problem category will use the MPTP2078 problem set. Precomputation and storage of information about problems in those sets, or their solutions, is not directly allowed. However, training as described above is allowed.

   • The competition panel may disqualify any system whose tuning or training is deemed to be problem specific rather than general purpose. If you are in doubt, contact the competition organizer.
4. The system's performance must be reproducible by running the system again.

1. Systems must run on a single locally provided standard UNIX computer (the competition computers). ATP systems that cannot run on the competition computers can be entered into the demonstration division.
2. Systems must be executable by a single command line, using an absolute path name for the executable, which might not be in the current directory. In non-batch divisions the command line arguments are the absolute path name of a symbolic link as the problem file name, the individual problem time limit (if required by the entrant), and entrant specified system switches. In batch divisions the command line arguments are the absolute path name of the batch specification file, the overall category time limit (if required by the entrant), and entrant specified system switches. No shell features, such as input or output redirection, may be used in the command line. No assumptions may be made about the format of file names.
3. Systems must be fully automatic, i.e., all command line switches have to be the same for all problems in each division.

1. In non-batch divisions all solution output must be to stdout. In batch divisions all solution output must be to the named output file for each problem.
2. In batch divisions the systems must print SZS notification lines to stdout when starting and ending work on a problem (including any cleanup work, such as deleting temporary files). For example

   % SZS status Started for /home/graph/tptp/TPTP/Problems/CSR/CSR075+2.p
     ... (system churns away, result and solution output to file)
   % SZS status Theorem for /home/graph/tptp/TPTP/Problems/CSR/CSR075+2.p
   % SZS status Ended for /home/graph/tptp/TPTP/Problems/CSR/CSR075+2.p

3. For each problem, the systems must output a distinguished string indicating what solution has been found or that no conclusion has been reached. Systems are expected to use the SZS ontology and standards for this. For example

   % SZS status Theorem for SYN075+1

   or

   % SZS status GaveUp for SYN075+1

   The distinguished strings must be different for:
   • Proved theorems of FOF problems (SZS status Theorem)
   • Disproved conjectures of FNT problems (SZS status CounterSatisfiable)
   • Unsatisfiable sets of formulae (FOF problems without conjectures) and unsatisfiable set of clauses (CNF problems) (SZS status Unsatisfiable)
   • Satisfiable sets of formulae (FNT problems without conjectures) and satisfiable set of clauses (SAT problems) (SZS status Satisfiable)
   The first distinguished string output is accepted as the system's result.

   In batch divisions this line must use the SZS standards, including the problem file name, and must be output to both stdout and the solution file. In batch divisions this line must be output as the last thing before the ending notification line.

4. When outputting proofs/models, the start and end of the proof/model must be delimited by distinguished strings. Systems are expected to use the SZS ontology and standards for this. For example

   % SZS output start CNFRefutation for SYN075+1
     ...
   % SZS output end CNFRefutation for SYN075+1

   The distinguished strings must be different for:
   • Proofs (SZS output forms Proof, Refutation, CNFRefutation)
   • Models (SZS output forms Model, FiniteModel, InfiniteModel, Saturation)
   The string specifying the problem status must be output before the start of a proof/model. Use of the TPTP format for proofs and finite interpretations is encouraged.

1. The systems that run on the competition computers must be interruptible by a SIGXCPU signal, so that the CPU time limit can be imposed, and interruptable by a SIGALRM signal, so that the wall clock time limit can be imposed. For systems that create multiple processes, the signal is sent first to the process at the top of the hierarchy, then one second later to all processes in the hierarchy. The default action on receiving these signals is to exit (thus complying with the time limit, as required), but systems may catch the signals and exit of their own accord. If a system runs past a time limit this is noticed in the timing data, and the system is considered to have not solved that problem.
2. If an ATP system terminates of its own accord, it may not leave any temporary or intermediate output files. If an ATP system is terminated by a SIGXCPU or SIGALRM, it may not leave any temporary or intermediate output files anywhere other than in /tmp. Multiple copies of the ATP systems must be executable concurrently, in the same (NFS cross mounted) directory. It is therefore necessary that temporary files have unique names.
3. For practical reasons excessive output from an ATP system is not allowed. A limit, dependent on the disk space available, is imposed on the amount of output that can be produced. The limit is at least 10MB per system.

System Delivery

• Instructions for installation. Systems are expected to use the proposed TPTP ATP System Building Conventions for their installation.
• Instructions for executing the system, using %s and %d to indicate where the problem file name and time limit must appear in the command line.
• The distinguished strings indicating what solution has been found, and delimiting proofs/models.

For systems that do not use the proposed TPTP ATP System Building Conventions, the installation procedure may require changing path variables, invoking make or something similar, etc., but nothing unreasonably complicated. All system binaries must be created in the installation process; they cannot be delivered as part of the installation package. If the ATP system requires any special software, libraries, etc, which is not part of a standard installation, the competition organizers must be told in the system registration. The system is installed onto the competition computers by the competition organizers, following the instructions in the ReadMe file. Installation failures before the system delivery deadline are passed back to the entrant (i.e., delivery of the installation package before the system delivery deadline provides an opportunity to fix things if the installation fails!). After the system delivery deadline no further changes or late systems are accepted. If you are in doubt about your installation package or procedure, please email the competition organizers.

For systems running on entrant supplied computers in the demonstration division, entrants must deliver a source code package to the competition organizers by the start of the competition. The source code package must be a .tgz file containing the system source code.

After the competition all competition division systems' source code is made publicly available on the CASC web site. In the demonstration division, the entrant specifies whether or not the source code is placed on the CASC web site. An open source license is encouraged.

System Execution

During the competition a perl script parses the systems' outputs. If any of an ATP system's distinguished strings are found then the time used to that point is noted. A system has solved a problem iff it outputs its termination string within the time limit, and a system has produced a proof/model iff it outputs its end-of-proof/model string within the time limit. The result and timing data is used to generate an HTML file, and a web browser is used to display the results.

The execution of the demonstration division systems is supervised by their entrants.

System Checks for Non-Batch Division Systems

• Check: The ATP system can run on a computer that has the same configuration as the competition computers.

• Check: The ATP system can be run by an absolute path name for the executable.

  prompt> pwd
  /home/tptp
  prompt> which MyATPSystem
  /home/tptp/bin/MyATPSystem
  prompt> /home/tptp/bin/MyATPSystem /home/tptp/TPTP/Problems/SYN/SYN075-1.p
  SZS status Unsatisfiable for SYN075-1
       

• Check: The ATP system accepts an absolute path name of a symbolic link as the problem file name.

  prompt> cd /home/tptp/tmp
  prompt> ln -s /home/tptp/TPTP/Problems/SYN/SYN075-1.p CCC001.p
  prompt> cd /home/tptp
  prompt> /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001.p
  SZS status Unsatisfiable for CCC001
       

• Check: The ATP system makes no assumptions about the format of the problem file name.

  prompt> ln -s /home/tptp/TPTP/Problems/SYN/SYN075-1.p _foo-Blah
  prompt> /home/tptp/bin/MyATPSystem _foo-Blah
  SZS status Unsatisfiable for _foo-Blah
       

• Check: The ATP system can run under the RunSolver program.

  > which runsolver
  /home/tptp/bin/runsolver
  prompt> /home/tptp/bin/runsolver -w /dev/null -C 200 -W 400 --delay 1 --timestamp --add-eof /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001.p
  SZS status Unsatisfiable for CCC001
       

• Check: The ATP system's CPU time can be limited using the RunSolver program.

  prompt> /home/tptp/bin/runsolver -w /dev/null -C 20 -W 40 --delay 1 --timestamp --add-eof /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001.p
  CPU time limit exceeded
       

• Check: The ATP system's wall clock time can be limited using the RunSolver program.

  prompt> /home/tptp/bin/runsolver -w /dev/null -C 20 -W 10 --delay 1 --timestamp --add-eof /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001.p
  Alarm clock
       

• Check: The system outputs a distinguished string when terminating of its own accord.

  prompt> /home/tptp/bin/runsolver -w /dev/null -C 200 -W 400 --delay 1 --timestamp --add-eof /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001.p
  SZS status Unsatisfiable for CCC001
  FINAL WATCH: 147.8 CPU 150.0 WC
       

  Similar checks should be made for the cases where the system gives up.

• Check: The system outputs distinguished strings at the start and end of its solution.

  prompt> /home/tptp/bin/runsolver -w /dev/null -C 200 -W 400 --delay 1 --timestamp --add-eof /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001.p
  SZS status Unsatisfiable for CCC001
  SZS output start CNFRefutation for CCC001
      ... acceptable proof/model here ...
  SZS output end CNFRefutation for CCC001
  FINAL WATCH: 147.8 CPU 150.0 WC
       

• Check: No temporary or intermediate files are left if the system terminates of its own accord, and no temporary or intermediate files are left anywhere other than in /tmp if the system is terminated by a SIGXCPU or SIGALRM. Check in the current directory, the ATP system's directory, the directory where the problem's symbolic link is located, and the directory where the actual problem file is located.

  prompt> pwd
  /home/tptp
  prompt> /home/tptp/bin/runsolver -w /dev/null -C 200 -W 400 --delay 1 --timestamp --add-eof /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001.p
  SZS status Unsatisfiable for CCC001
  FINAL WATCH: 147.8 CPU 150.0 WC
  prompt> ls /home/tptp
      ... no temporary or intermediate files left here ...
  prompt> ls /home/tptp/bin
      ... no temporary or intermediate files left here ...
  prompt> ls /home/tptp/tmp
      ... no temporary or intermediate files left here ...
  prompt> ls /home/tptp/TPTP/Problems/GRP
      ... no temporary or intermediate files left here ...
  prompt> ls /tmp
      ... no temporary or intermediate files left here by decent systems ...
       

• Check: Multiple concurrent executions do not clash.

  prompt> (/home/tptp/bin/runsolver -w /dev/null -C 200 -W 400 --delay 1 --timestamp --add-eof /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001.p) & (/home/tptp/bin/runsolver -w /dev/null -C 200 -W 400 --delay 1 --timestamp --add-eof /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC002.p)
  SZS status Unsatisfiable for CCC001
  
  SZS status Unsatisfiable for CCC002