# Design and Organization

This document contains information about the:

The rules, specifications, and deadlines given here are absolute. Only the competition panel has the right to make exceptions. It is assumed that all entrants have read the web pages related to the competition, and have complied with the competition rules. Non-compliance with the rules can lead to disqualification. A "catch-all" rule is used to deal with any unforeseen circumstances: No cheating is allowed. The panel is allowed to disqualify entrants due to unfairness, and to adjust the competition rules in case of misuse.

### Disclaimer

Every effort has been made to organize the competition in a fair and constructive manner. No responsibility is taken if, for one reason or the other, your system does not win.

## Changes

The design and procedures of this CASC evolved from those of previous CASCs. Important changes for this CASC are:
• The THN and TFN divisions have been added.

• The LTB division has returned from its one year hiatus.

• The UEQ division has returned to its hiatus state.

## Divisions

CASC is divided into divisions according to problem and system characteristics. There are competition divisions in which systems are explicitly ranked, and a demonstration division in which systems demonstrate their abilities without being ranked. Some divisions are further divided into problem categories, which makes it possible to analyse, at a more fine grained level, which systems work well for what types of problems. The problem categories have no effect on the competition rankings, which are made at only the division level.

### Competition Divisions

The competition divisions are open to ATP systems that meet the required system properties. Each division uses problems that have certain logical, language, and syntactic characteristics, so that the ATP systems that compete in the division are, in principle, able to attempt all the problems in the division.
• The THF division: Typed Higher-order Form theorems (axioms with a provable conjecture). The THF division has two problem categories:
• The TNE category: THF with No Equality
• The TEQ category: THF with EQuality

• The THN division: Typed Higher-order form Non-theorems (axioms with a countersatisfiable conjecture, and satisfiable axiom sets). The THN division has two problem categories:
• The TNN category: THN with No equality
• The TNQ category: THN with eQuality

• The TFA division: Typed First-order with Arithmetic theorems (axioms with a provable conjecture). The TFA division has three problem categories:
• The TFI category: TFA with only Integer arithmetic
• The TFR category: TFA with only Rational arithmetic
• The TFE category: TFA with only Real arithmetic

• The TFN division: Typed First-order with arithmetic Non-theorems (axioms with a countersatisfiable conjecture, and satisfiable axiom sets). The TFN division has three problem categories:
• The TIN category: TFA with only Integer arithmetic
• The TRN category: TFA with only Rational arithmetic
• The TEN category: TFA with only Real arithmetic

• The FOF division: First-Order Form theorems (propositional, 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 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). Effectively propositional means that the problems are known to be reducible to propositional problems, e.g., CNF problems that have no functions with arity greater than zero. 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 theorems (axioms with a provable conjecture) from Large Theories, presented in Batches. A large theory has many functors and predicates, and many axioms of which typically only a few are required for the proof of a theorem. Problems in a batch all use a common core set of axioms, and the problems in a batch are given to the ATP system all at once. The LTB division has four problem categories:
• The HLL category: Problems exported from HOL Light.
• The HL4 category: Problems exported from HOL4.
• The ISA category: Problems exported from Isabelle.
• The MZR category: Problems exported from Mizar.

The problems section explains what problems are eligible for use in each division and category. The system evaluation section explains how the systems are ranked in each division.

### Demonstration Division

ATP systems that cannot run in the competition divisions for any reason (e.g., the system requires special hardware, or the entrant is an organizer) can be entered into the demonstration division. Demonstration division systems can run on the competition computers, or on computers supplied by the entrant. The entry specifies which competition divisions' problems are to be used. The demonstration division results are presented along with the competition divisions' results, but might not be comparable with those results. The systems are not ranked and no prizes are awarded.

## Infrastructure

### Computers

The non-LTB divisions' computers have:
• Four (a quad-core chip) Intel(R) Xeon(R) E5-2609, 2.40GHz CPUs
• 256GB memory
• The Red Hat Enterprise Linux Workstation release 6.3 (Santiago) operating system, kernel 2.6.32-431.1.2.el6.x86_64
The LTB division's computers have:
• 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
Each ATP system runs one job on one computer at a time. Systems may use all the cores on the computers (although this does not necessarily help, because a CPU time limit is imposed).

### Problems

Problem Selection
Problems for the non-LTB divisions are taken from the TPTP Problem Library. The TPTP version used for CASC is not released until after the competition has started, so that new problems have not been seen by the entrants. The problems have to meet certain criteria to be eligible for selection. The problems used are randomly selected from the eligible problems based on a seed supplied by the competition panel.
• The TPTP tags problems that designed specifically to be suited or ill-suited to some ATP system, calculus, or control strategy as {\em biased}, and they are excluded from the competition.
• The problems have to be syntactically non-propositional.
• The TPTP uses system performance data to compute problem difficulty ratings \cite{SS01}. The difficulty rating is based on ATP system performance data in the Thousands of Solutions from Theorem Provers (TSTP) solution library, and ranges from 0.00 (easy) to 1.00 (unsolved). 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 if there are not enough problems with ratings in that range. 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 selection is constrained so that no division or category contains an excessive number of very similar problems.
• The selection 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.
The problems are given to the ATP systems in TPTP format, with no preprocessing. Problems for the LTB division are taken from publicly available problem sets: the HLL problem category will use the HH7150 problem set; the HL4 problem category will use the H4H13897 problem set; the ISA problem category will use the SH5795 problem set; the MZR problem category will use the MPTP2078 problem set. The problems in each category have consistent symbol usage, and almost consistent axiom naming, between problems. The problems in each category have a large number of common {\tt include}d axiom files (the "common core set of axioms"). Systems can benefit from preloading and analyzing these common axioms once, in advance of problem solving. In order to facilitate and promote learning from previous proofs, each problem category is accompanied by a set of training problems and their solutions, which can be used for tuning and training during (typically at the start of) the competition. Entrants are expected to honestly not use any other of the (publicly available) problems for tuning or training before the competition. The problems have to meet certain criteria to be eligible for selection. The problems used are randomly selected from the eligible problems based on a seed supplied by the competition panel.
• Problems that are solvable in 60s by at least one of the non-LTB versions of the systems are used for the training sets.
• Problems that were used in training sets are not eligible.
• Problems that are solvable in 60s by at least one of the non-LTB versions of the systems are eligible for the first round. 70% of the selected problems will from this group.
• Problems that are not solvable in 60s by any of the non-LTB versions of the systems are eligible for the second round. 30% of the selected problems will from this group.

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

It is a lower bound on the total number of problems because it assumes that every system uses all of the time limit for each problem. Since some solution attempts succeed before the time limit is reached, more problems can be used.

The numbers of problems used in each non-LTB 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. In the LTB division there will be at least 200 problems in each problem category.

Each batch specification consists of:
• 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
BatchSampleLTBHLL is an example. TrainingData.HLL.tgz contains all the files mentioned in that example. (Note here the training problems are the same as the competition problems, which will not be the case during CASC. Right now you should be able to train to perfection!)

### Resource Limits

Non-LTB divisions
CPU and wall clock time limits are imposed. The minimal CPU time limit per problem is 240s. The maximal CPU time limit per problem is determined using the relationship used for determining the number of problems, with the minimal number of problems as the NumberOfProblems. The CPU time limit is chosen as a reasonable value within the range allowed, and is announced at the competition. The wall clock time limit is imposed in addition to the CPU time limit, to limit very high memory usage that causes swapping. The wall clock time limit per problem is double the CPU time limit. An additional memory limit is imposed, depending on the computers' memory. The limits are imposed individually on each solution attempt.

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.

## System Evaluation

For each ATP system, for each problem, four items of data are recorded: whether or not the problem was solved, the CPU time taken, the wall clock time taken, and whether or not a proof or model was output. In the LTB division, the wall clock time is the time from when the system reports starting on a problem and reports ending on a problem - the time spent before starting the first problem, and times spent between ending a problem and starting the next, are not part of the time taken on problems.

The systems are ranked in the competition divisions, from the performance data. The THF, TFA, FOF, FNT, and LTB divisions are ranked according to the number of problems solved with an acceptable proof/model output. The THN, TFN, and EPR divisions are ranked according to the number of problems solved, but not necessarily accompanied by a proof or model (but systems that do output proofs/models are highlighted in the presentation of results). Ties are broken according to the average time taken over problems solved (CPU time for non-LTB divisions, wall clock time for the LTB division). In the competition divisions winners are announced and prizes are awarded.

The competition panel decides whether or not the systems' proofs and models are "acceptable". 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-LTB 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.
• 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 divisions ranked by the numbers of proofs/models output) 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.

## System Entry

To be entered into CASC, systems must be registered using the CASC system registration form. No registrations are accepted after the registration deadline. For each system entered, an entrant must be nominated to handle all issues (including execution difficulties) arising before and during the competition. The nominated entrant must formally register for CASC. It is not necessary for entrants to physically attend the competition.

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. Prover9 2009-11A is automatically entered into the FOF division, to provide a fixed-point against which progress can be judged.

### System Description

A system description must be provided for each ATP system entered, using this HTML schema. The schema has the following sections:
• 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 must be emailed to the competition organizers by the system description deadline. The system descriptions form part of the competition proceedings.

### Sample Solutions

For systems in the division that require proof/model output, representative sample solutions must be emailed to the competition organizers by the sample solutions deadline. Use of the TPTP format for proofs and finite interpretations is encouraged. The competition panel decides whether or not proofs and models are acceptable.

Proof/model samples are required as follows:

An explanation must be provided for any non-obvious features.

## System Requirements

### System Properties

Entrants must ensure that their systems execute in a competition-like environment, and have the following properties. Entrants are advised to finalize their installation packages and check these properties. well in advance of the system delivery deadline. This gives the competition organizers time to help resolve any difficulties encountered.

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 THN, TFN, 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. 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 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.
4. 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 other 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. Precomputation and storage of information about other problems in the LTB problem sets, or their solutions, is not allowed.
5. 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.
6. The system's performance must be reproducible by running the system again.
Execution
1. Systems in the non-LTB divisions must run on StarExec, and systems in the LTB division must run on the specified competition computers. ATP systems that cannot run on StarExec/competition computers can be entered into the demonstration division.
2. Systems must be fully automatic, i.e., all command line switches have to be the same for all problems/problem batches in each division.
3. In the LTB division the systems must attempt the problems in each batch in the order given in the batch specification file. Systems may not start any attempt on a problem, including reading the problem file, before ending the attempt on the preceding problem.
Output
1. In the non-LTB divisions all solution output must be to stdout. In the LTB division all solution output must be to the named output file for each problem.
2. In the LTB division 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 system must output a distinguished string indicating what solution has been found or that no conclusion has been reached. Systems must use the SZS ontology and standards for this. For example
% SZS status Theorem for SYN075+1
or
% SZS status GaveUp for SYN075+1
In the LTB division this line must be the last line output before the ending notification line (the line must also be output to the output file).
4. When outputting proofs/models, the start and end of the proof/model must be delimited by distinguished strings. Systems must 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 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.
Resource Usage
1. 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.
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.

### System Delivery

For systems in the non-LTB divisions, entrants must email a StarExec installation package to the competition organizers by the system delivery deadline. The installation package must be a .tgz file containing only the components necessary for running the system (i.e., not including source code, etc.). The entrants must also email a .tgz file containing the source code and any files required for building the StarExec installation package to the competition organizers by the system delivery deadline.

For systems running in the LTB division, entrants must email a {\tt .tgz} file containing the source code and any files required for building the executable system to the competition organizers by the system delivery deadline.

For systems running on entrant supplied computers in the demonstration division, entrants must email a {\tt .tgz} file containing the source code and any files required for building the executable system to the competition organizers by the system delivery deadline.

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

Execution of the ATP systems in the non-LTB divisions is controlled by StarExec. The jobs are queued onto the computers so that each computer is running one job at a time. All attempts at the Nth problems in all the divisions and categories are started before any attempts at the (N+1)th problems.

Execution of the ATP systems in the LTB division is controlled by a perl script, provided by the competition organizers. The jobs are queued onto the computers so that each computer is running one job at a time. All attempts in each category in the division are started before any attempts in the next category.

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 the non-LTB Divisions

• Check: You can login to StarExec. If not, apply for an account in the TPTP community.

• Check: You can access the TPTP space. If not, email the competition organizers.

• Check: You can create and upload a StarExec installation package. The competition organizers have examplar StarExec installation packages that you can use as a starting point - email the competition organizers to get one that is appropriate for your ATP system.

• Check: You can create a job and run it, and your ATP system gets the correct result. Use the SZS post processor.

• Check: Your ATP system can solve a problem that has include directives. Because of the way StarExec runs jobs, your ATP system must implement the TPTP requirement ... "Include files with relative path names are expected to be found either under the directory of the current file, or if not found there then under the directory specified in the TPTP environment variable."

• Check: You can email your StarExec installation package to the competition organizer for testing.