Tools for Optimality Theory

Tamás Biró

Version 1.0+epsilon


Table of content

1. Introduction
2. Basics and the example universe
3. Menu bar
4. Pop-up windows and details of the elements
5. Tricks, tips and miscellaneous topics
6. Running OTKit from command line
7. Scripting language
8. XML files, Java classes
9. Java library
10. Concluding remarks, acknowledgments, historical notes



1. Introduction

The goal of OTKit is to offer a number of tools for Optimality Theory (OT, cf. Prince and Smolensky 1993/2004), including its dialects and Harmonic Grammar (HG). Since 1993, OT has become very popular in linguistics, especially in phonology, but significant work has also been done in syntax, semantics and pragmatics. A great variety of software already exists for OTers, most of them focusing on a particular aspect, such as learning. OTKit tries to introduce new approaches and aspects, such as permitting infinite candidate sets, offering a large variety of forms (representations) and functions (constraints), and implementing the author's view on the competence–performance dichotomy. But first of all, on a didactic level, OTKit wishes to promote a more formal, computational understanding of the basic concepts of Optimality Theory, in general.

OTKit has two basic components: a graphical user interface and a Java library. The user interface may be a good starting point for beginners, including undergrad students of linguistics. Yet, hopefully many linguists will also find it useful for their research. More advanced users may write their own scripts and their own XML specifications, and then run their experiments from command line. Researchers with some programming experience will then shift to the Java library, the most efficient and most elaborate tool of this tool kit.

Notwithstanding some differences, both the user interface and the Java library share their view of OT concepts. For instance, both make the distinction between forms (a string, a tree, a set of counters, an AVS, etc.) and candidates (a pair of forms – the underlying form and the surface form – in the simplest case). Both see the constraints as functions on the candidates, and both allow several "ranking variables" within a single hierarchy, which however must be typed (either "OT" or "HG"). So the user interface is also an introduction to the "conceptual decomposition" of Optimality Theory proposed by the author, whereas the Java library offers a much more flexible tool to implement one's own linguistic model within this framework.

The remark regarding the Java library being more flexible and powerful than the user interface is especially true at the time of publishing OTKit version 1.0 (January 2010), since the development of the user interface (including the scripting language) lags far behind the Java library. Much of linguistic performance and some of the learning algorithms are already implemented in the library, while the user interface only allows for the definition of the most basic components of OT (simple forms, candidates, a larger variety of constraints, hierarchies and very simple Gen functions) together with some simple actions.

It is not a secret that the main motivation for developing OTKit has been selfish: to have fun, to teach myself Java and to support my own research. Consequently, it follows my own approach to Optimality Theory and it promotes my Simulated Annealing for Optimality Theory Algorithm (SA-OT). This fact does not exclude however that other approaches have been or will be included – also depending on your feedback. As the product of an autodidactic programmer, OTKit certainly suffers from a number of children's illnesses in the way functions have been implemented, but also from many bugs. Users are therefore emphatically encouraged to report any remark they have: bugs, missing functionalities, details that slow down the program unnecessarily, gaps and typos in the documentation, and so forth. Similarly useful will be if users also provide feedback on the types of tools they need for their own research: what kinds of representations (inner structures of the candidates), of constraints, or of learning algorithms you would like to see in OTKit? I cannot guarantee that each and every need can and will be met, but I will try to do my best to implement recurring suggestions.

Basic references to Optimality Theory (aka "where to start" or "what you must have heard of"):

Alan Prince and Paul Smolensky (1993/2002/2004). Optimality Theory: Constraint Interaction in Generative Grammar. Rutgers University Center for Cognitive Science Technical Report 2 (1993). ROA-537 (2002). Blackwell Publishing (2004).
The Rutgers Optimality Archive, containing over a thousand articles on OT.
Bruce Tesar and Paul Smolensky (2000). Learnability in OT. MIT Press.
Paul Boersma and Bruce Hayes (2001). 'Empirical Tests of the Gradual Learning Algorithm'. Linguistic Inquiry 32: 45-86.
Paul Smolensky and Géraldine Legendre (2006). The Harmonic Mind. MIT Press.
René Kager (1999). Optimality Theory. Cambridge University Press.
John J. McCarthy (2008). Doing Optimality Theory. Applying Theory to Data. Blackwell Publishing.

Some other software for Optimality Theory:

Praat: doing phonetics by computer by Paul Boersma and David Weenink.
OTSoft by Bruce Hayes.
OT-Help by Michael Becker, Joe Pater and Christopher Potts.
Maxent Grammar Tool by Bruce Hayes.
SA-OT demo by Tamás Bíró.
RCD – The Movie by Alan Prince.
PyPhon by Jason Riggle.

This manual focuses first (and foremost) on general concepts (sections 2 and 5) and the OTKit user interface (sections 3 and 4). The script language, the XML format and the Java library are introduced only afterward, mainly by pointing to their documentations. A general introduction to Optimality Theory based on the "conceptual decomposition" used in OTKit should be the topic of a separate book; as long as it is not written, many details are to be recovered bits by bits from the documentation (this manual, the javadoc and the help texts in the graphical user interface), or to be asked directly from me.


2. Basics

2.1 Launching the program

Besides being a Java library for the advanced programmer, OTKit is also a Java program, which requires Java 1.6 (Java Runtime Environment JRE 6) be installed on your computer. Nowadays that is not a problem: your computer most probably has it, unless you have disabled it; or you use some obscure operating system or an antediluvian machine. Otherwise, the runnable jar file OTKit.jar should work. Click on it, or type java -jar OTKit.jar in the command line, whichever is applicable. The files created by/for OTKit (script files, XML files, output files) must also be transferable from one operating system to another. (Although the end-of-line characters may cause problems.)

OTKit can be used in two ways: either executing scripts from command line or launching its graphical user interface. Beginners (and many advanced users) will prefer the second, more user friendly option. Defining elements (forms, candidates, constraints,...) is possible either via the menu items and pop-up windows in the graphical interface, or via the scripting language, or via files in the OTKit XML format. When creating an element in the user interface, you will save it in the XML format, or save the history containing the script command creating that element. (To get a first impression about the XML format and the scripting language, look at the content of the files saved in this way, or look at the example script files and at the example XML files on the website.) The user interface is able to load script files and XML files, and scripts can also read and write files. The output of your actions in the user interface appears in the main window (that can be saved to an output file), while the actions in scripts pour their result to the standard output stream.

Actions and elements are thus two key concepts in OTKit. But before discussing them, let us first turn to the graphical user interface.

2.2 The graphical user interface

The graphical user interface is composed of three parts: the menu bar, an output window and a line for entering commands.

OTKit primarily "speaks" to you via the output window. Always check its content as that is where you will find error messages, confirmation of some of your actions (for instance, "constraint X created"), as well as the output of your experiments. You can copy-paste (some of) its content to your favorite text editor, or save it to a plain text file (using the "save output" item within the File menu). If you run OTKit without the graphical interface, the standard output stream – together with the standard error – will correspond to the output window.

In the bottom line of the graphical interface you are invited to have your first experiments with script commands. For instance, type help() (including the parenthesis) to get a first aid. Reading the answer of OTKit in the output window, you will learn that typing help(script) will provide you with more script commands, such as exit() or history().

In fact, most of what you will have done (such as creating a constraint, reading a file or learning a hierarchy) is recorded in the history – either you will have typed them into the bottom command line, or done them using the menu items and pop-up windows. The history itself is a correct script. So by listing the history in the output window – using the history() command – or saving it to file ("save history" within the File menu) you can both learn more on the OTKit scripting language and you can simply repeat your experiments in the future. (Users familiar with Praat will know this trick.) Executing a script, for instance a history saved to file, is possible via the "load script" menu item in the File menu.

Details of the rest of the menu system are discussed in section 3. The pop-up windows opened by them are presented in section 4. But in order to better understand them, we first have to discuss the elements in general.

2.3 Elements, universes and actions

Before turning to the details of the menu bar, we have to introduce three concepts: the elements, the universe and the actions.

First, elements are the basic objects that we have to define: candidates, constraints, hierarchies, learning methods, production methods, experiments, and so on. Actually, not everything needs to be defined explicitly. For instance, by defining a Gen function, you also define candidates in an implicit way. In random walk performance models, the candidate set is defined by a possibly very small Gen (defining the starting point of the random walk) and the topology determining how to find the neighbors of the candidates already reached by the walker. At the same time, certain elements are to be defined only because they are needed to define other elements. For instance, candidates and not forms are used in Optimality Theory; but candidates are made of forms (of an underlying form and of a surface form), and so forms have to be introduced just to become building blocks of candidates.

As mentioned, an element can be introduced either in some pop-up window opened in the menu bar, or via some scripting command, or by an XML document. Often, schemes are offered (which themselves are organized into scheme types), which possibly await for some parameter values to create an element. For instance, the constraint scheme *Initial_P1 can be found within the scheme type "string constraints"; namely, it applies to candidates (surface forms) consisting of a string of characters. The way to obtain an actual constraint from this scheme is filling its parameter P1. In this case P1 can be any string; in other cases, parameters must be filled with a number or an integer number. The combination of this scheme with a parameter value results in a constraint that is violated if and only if the surface form string starts with the value of P1.

Whatever you have defined explicitly is collected in your MyUniverse. A separate menu helps you maintaining it: loading it, saving it, deleting old elements from it, or redefining the elements in it. Importantly, each element has a unique name, and no two elements of the same category (two constraints, two hierarchies, etc.) may have the same name. So if you create (or import) a constraint to which you assign the name of an already existing constraint, the old one will be deleted from MyUniverse. Luckily, if you make such a mistake, or if you delete an element of MyUniverse, it will not be definitively lost: you may find it in another universe, the TrashUniverse from where you can recover it to MyUniverse. Make sure not to overwrite another element again, when you move the almost lost element back to MyUniverse. Moreover, if the item being deleted from MyUniverse deletes another item already residing in TrashUniverse, this second one will be lost for good.

The "Organize & Save" window is where you find everything currently in MyUniverse. That is where you can delete elements, after having selected them. That is also where you can open elements to view their inner structure: for instance, their schemes and parameter values. If you open an element for editing, you change its parameters and save the result under a different name, you have created a slightly different element. Similarly, saving the element under a different name and then removing the original one from MyUniverse is the way you can rename an element.

Elements that you have created and which reside in MyUniverse can be saved to an XML file. The "Organize & Save" window offers the possibility to save selected elements. The "Save all" window in the same menu speeds up the process of saving everything currently in MyUniverse. Additionally, single elements can also be saved in the windows defining them.

Later, these OTKit XML files, as well as those you write yourself, can be loaded to OTKit. The "Load" window in the MyUniverse menu displays the elements in the XML document, so that you can load them separately to MyUniverse; or open them for editing (changing their name, for instance) before moving them to MyUniverse. The "Load all" window loads a full file into MyUniverse in one step.

The XML format complements the script language: both can spare you the time needed to re-generate the universe, but the XML format focuses on the elements having been created, whereas the script focuses on the operations creating them. Both encode the information needed to create the element, which you also have to specify in the pop-up window defining it: its name in all cases, as well as other information, such as the scheme used and the parameter values.

Finally, the elements residing in MyUniverse would not be worth a penny, unless you could use them in experiments. Hence, you need actions: the application of a constraint to a certain candidate, or the generation of an OT tableau, running a learning algorithm, and so forth. Actions are found in the menu system and in the script language.

2.4 The Example Universe

In the Help menu, you can click on "Load example universe" in order to facilitate your first steps. Having loaded it, open the "Organize & Save" window (within "MyUniverse") to see what this universe contains. Now you can start playing with it: click, for instance, on the "view/edit" buttons. Observe in each case which scheme is being used with what parameters. Why not try altering them, or defining new elements? Subsequently, go and perform experiments in the "competence" and "actions" menus.

A few words about the example. It is about a simple language over the alphabet {a, i, u, p, t, b, d}. The first element in the universe is the table "alphabet", which contains these letters (in fact, singleton strings). This table is used to create Gen functions.

The universe contains three different Gen functions: Table_alphabet_star maps any underling form to the infinite set of all possible strings created from these seven characters (including the empty string, that is, the string of length 0). Gen alphabet^4 restricts this set to those of four letters, and Gen From_table_restricted_gen to four specific strings. The previous Gen employs the Table_P1_power_P2 scheme, P1 being "alphabet" and P2 being "4". The latter one is based on Table restricted_gen, also present in MyUniverse, and on scheme Strings_in_table_P1. Both schemes require the name of a table as their parameter, but use those tables differently.

You will also find a few forms and candidates in the universe. The forms contain strings of length 4, and the candidates contains underlying forms and surface forms, each being a string of length 4. Observe that candidate /uptu/ [upda] uses the scheme that interprets its parameters as the string that are going to become the underlying form and the surface form. Differently, candidate /uptu/ [uptu] employs the scheme that requires the names of already defined forms in MyUniverse. Actually, there is no form yet containing the string upda, so one should create it first to be able to use the second scheme to create a candidate equivalent to the first candidate above. In fact, many schemes come in pairs: a string (a parameter, or a cell in the table specified in a parameter) can be interpreted either as the content of a new form, or as the name of a previously defined form. At this point is seems superfluous to create forms and then create candidates using the second scheme; but if you used more complex forms (counters, trees, AVSs...), this step would become necessary.

As a simple task, let us test whether the candidate being optimal for a more restricted Gen is also optimal for a less restricted one. For that purpose, we obviously need constraints and a hierarchy. Hierarchy hier1 is of type "OT", and realizes the following ranking:

Assimilate[voice] >> Max(b) >> Assimilate[place] >> *high >> Dep >> Max(C) >> Max(V)

The scheme employed for the two assimilation constraints refers to table prohibited_clusters. This table has three columns: the first one contains consonant clusters, the second one contains the violations assigned by constraint Assimilate[voice], and the third one the violations by constraint Assimilate[place]. This table could be seen as a mini tableau with yet unranked constraints, but the first column only contains substrings of the surface forms. The two assimilation constraints are realized by referring to this table (the table's name being their P1), and using the column number ("2" or "3") as their P2.

Constrains *high, Max(C) and Max(V) employ schemes summing up previously defined constraints; that is the reason why MyUniverse contains more constraints than the hierarchy. For more examples of constraint arithmetic see the section on various tricks below.

Before runing the experiment, can you predict with a paper and a pen which candidate shall be the winner? Check your prediction using the "Grammaticality judgment" function in the Competence menu. Your prediction is correct if OTKit tells you that the candidate is grammatical; although there may be more grammatical forms. Are you not sure about how these constraints assign their violation marks to the candidates? (Are the descriptions of the constraint schemes not clear? Send me an email!) You can also check the constraints' behavior using the "Apply constraint" function among the "Actions". That is also where you should check whether the constraints you define really do what you want them to do.

Afterwards, check what OTKit finds ("Grammatical outputs"). Note that in the case of the infinite Gen function you must specify the maximal number of candidates to be considered. The candidates are listed starting with the shortest ones, and so you have to include at least 1+7+7^2+7^3+7^4 = 2801 candidates to have all surface forms of length 4 included. Remember also that having the corresponding tableau drawn takes much longer than finding the best candidate(s); so do not press that button before having experimented with smaller candidate sets.

Finally, let us use Gen as the vocabulary (lexicon, 'base') of the language: a list of underlying forms. The window "Full language" within the "Competence" menu will compute the surface forms actually appearing in the language, each corresponding to some underlying form in the base. If the same restricted Gen is also used as the OT Gen function, then we obtain an interesting language: surface form [ubdu] is used for both /ubdu/ and /ubtu/, whereas [uptu] corresponds to /uptu/; but /updu/ can be equally expressed as [uptu] or [ubdu].


3. Menu bar

The menu bar of the graphical interface includes the following items:


MyUniverse: load, save and organize your elements

Define: introduce new elements






4. Pop-up windows and details of the elements

In many cases, a "help" button has been added to the pop-up windows. Pressing it, you will find ample information in the main communication panel. Here I focus on some generalities.

Ignoring the basic communication windows (such as those browsing in the file system), we can sort most of the pop-up windows into three major groups.

The "horizontal windows" include those defining a form, a candidate, a constraint and a Gen function. They are to be read left to right. First choose a scheme type and then a scheme. Read the information appearing in the description box. Alternatively, load an element from MyUniverse or from a file, and check its scheme. Once you have a scheme, fill in the parameter[s]. Then, it is useful to click on "apply" to check if the parameters can be parsed correctly. The "apply" button will also suggest a name: the scheme's name, with P1, P2, etc. being replaced by their values. At this point, you may want to change the name. If you do not click on "apply", do not forget to specify the name. Once done, click on "add to MyUniverse", so that the newly defined element be saved there. You can also save this single element to a file.

The second type of windows can be called "vertical" ones. The "Organize & Save" windows for MyUniverse and TrashUniverse contain a list of elements. The window defining a table contains a list of rows; the one defining a hierarchy contains a list of constraints. In each case, checkboxes are used to remove rows and columns, or elements, or constraints and ranking variables.

The third type includes windows in which buttons help you load candidates, constraints, gen functions or hierarchies from MyUniverse, before you can execute some actions: calculate the grammatical forms, draw tableaux, and so forth.

As mentioned, most windows also include a "help" button, offering more support in the main window.

4.2 The "Options" window

In this window, you can set a number of useful details. Some of them affect the general functions of OTKit.

A number of options concern the way tables and tableaux are drawn. Depending on how you will use the output, you may want to change them. For instance, if you are a LaTeX user, you probably would like to spare editing the source file as much as possible. If you are going to import the table to Word, you may want to include symbols that you are going to employ when using Word's "convert text to table" functionality ("separate text at" => "other" => type, e.g., '&').

Default directory: The directory that is used whenever you open or save a file.
Column separator symbol: Symbol to be used to separate columns in tables and tableaux. The default setting '&' is most useful for LaTeX users. MS Office users can use the "convert text to table" function with '&' as the separator. For plain text format, you may prefer setting '|'.
End of row symbol: Most users will leave this field empty, and thus a new line will represent a row. Yet, LaTeX users might also want to have '\\' or '\cr \hline' attached.
Pointing hand symbol: Symbol used to point to the best candidate in a tableau.
Bang symbol: Symbol used to highlight the fatal violation in a tableau. Some wish to leave this field empty.

Pressing the 'ok' button will both save the settings ('apply') and close this window ('cancel').


5. Tricks, tips and miscellaneous topics

5.1. Forms and candidates

OTKit makes the distinction between forms and candidates. Forms are intermediary data structures that depend on the specific linguistic phenomenon and framework you work with. Candidates are collections of forms.

In the simplest case, a form is a string of characters. OTKit also offers the possibility of using "counters". A counter is a field for a number, such as the number of epentheses in the word, or the number of empty syntactic heads. It may often be simpler not to spell it out explicitly in a string, just to use a counter, and to use constraints reflecting on the values of the counters. In the future, I plan to enrich the repertoire of forms, including objects such as syntax trees, attribute-value structures, parses in metrical phonology, and so on.

A candidate is typically a pair of forms: an underlying form and a surface form. Sometimes the underlying form can be ignored during the experiment, hence the candidate scheme type "surface form only". More complex candidates are also possible, such as Paul Boersma's model with five layers (morpheme, underlying form, surface form, auditory form and articulatory form). As a rule, the domain of constraints are candidates. Therefore, chains of forms are also considered as single candidates, as long as constraints apply on chains as a whole.

Obviously, the simplest candidate is a "surface form-only" candidate, with a surface form that consists of a single string. Probably, many users will work with such simple models. Note that such a model does not deny the existence of an underlying form; the latter is simply not made explicit for the sake of simple and more efficient computations. Still, the three layers should be kept apart: the string, the form and the candidate are conceptually different, even if in practice they may not differ.

5.2. Hierarchies

A hierarchy of constraints is a set of ranked constraints, as well as a type. The type (practically, either OT or HG) tells you how to interpret the ranks. If the type is OT, then a ranking variable called "rank" sorts the constraints, the one having a higher rank being more influential. If, however, the type is HG, then another ranking variable, this one called "weight", determines the way the violations are to be summed up. Notice that the range of the constraints are typically positive (the number of "stars"), so the weights are negative.

In addition, a hierarchy may include further ranking variables. For instance, "unperturbed rank", to which a noise is added in Boersma's stochastic OT to obtain another ranking variable, the "perturbed rank". Each constraint in a hierarchy has a value for each of the ranking variables. Ranking variables can be copied or transformed in different ways: beside the "perturbation of the unperturbed rank", ranks can also be transformed into exponential weights, and vice-versa.

A ranking variable implies an order on the constraints. Usually, the greater the value of a ranking variable for some constraint, the higher it is ranked in the constraint hierarchy. As the weights have negative values, the ranking direction is reversed there: the lesser ("the more negative") the weight, the more influential that constraint. The ranking variable "setrank" has no numeric values: each constraint receives a string, seen as a set of characters. A constraint is higher ranked than another one, if the setrank of the first constraint is a superset of the setrank of the second one. Thereby it is possible to encode partially ordered constraints.

Note that at this moment only ranking variables "rank" and "weight" have any use: as explained above, they determine grammaticality in OT and HG grammars, respectively.

5.3. Constraint arithmetic

Constraints are best seen as functions on candidates. See for instance in my 2006 dissertation, page 168, fn. 9. The same idea also appears in John McCarthy's Doing Optimality Theory, 2008, p. 175:

In my opinion, every constraint definition should begin with the words "Assign one violation mark for every...". [...] An OT constraint has just one job: to assign some number of violation marks to a candidate based on its output structure or how it differs from the input. Any proposed constraint definition that fails to do this – and to do so unambiguously – is obviously problematic.

Software implementations of Optimality Theory will hopefully force linguists to view constraints as functions, and so to follow McCarthy's (and my own) suggestions, avoiding the traditional format: "In order not to violate the constraint, candidates must satisfy the following condition...".

If constraints are functions, then operations typical of functions can also be applied to constraints. For instance, if the range of the constraints are integers or real numbers, then you can sum or multiply them, and thereby define new constraints. If Boolean constraints are realized as a {0, 1} valued function, then the minimum and maximum operation corresponds to logical conjunction and disjunction (not to local conjunction!).

OTKit can only provide a limited number of constraints. Yet, by using the constraints of type "constraint arithmetic", you can do much more. Do you need a constraint that assigns one violation mark to candidate A and to candidate B, two violations to candidate C, and no marks to all other candidates? Use the constraint scheme "Cand_P1_gets_P2" to create three constraints: "Cand_A_gets_1", "Cand_B_gets_1" and "Cand_C_gets_2". The constraint you are looking for can be obtained by summing up these three constraints using scheme "Sum_P1".

Do you need a constraint that is violated by all candidates (one violation mark), except by candidate A? First, create two constraints: "Cand_A_gets_-1" (scheme "Cand_P1_gets_P2" applied to P1 = A and P2 = -1), as well as a constant constraint of value 1 (scheme "Constant_P1", also among the constraint arithmetic constraints). Then, have scheme "Constr_P1_+_Constr_P2" sum them. The result is a constraint that assigns 0 to candidate A, and 1 to all other candidates. Observe that constraint "Cand_A_gets_-1" generalizes the concept of a constraint, as typical linguistic constraints are neither constant, nor do they assign -1 violation marks.

Here is a more complex example. OTKit provides a constraint whose value is the value of counter 1 of the surface form. Now suppose that the counter in your candidates (surface forms) can only have non-negative integer values, counting the presence of some compulsory constituent. Suppose also that you need a constraint that assigns one violation mark if the value of the counter is 0, and no violation mark otherwise. This would be the constraint requiring the presence of that compulsory constituent. What do you do?

First, create a constraint named C that returns the value of counter 1. You can do that using the constraint scheme "Counter1". Then, use constraint scheme "P1_*_Constr_P2" to multiply it with -1. Let's name the resulting constraint minusC. Now, applying scheme "Constraint_P1_max_Constraint_P2" with P1 being minusC and P2 being the constant constraint "-1", will result in a constraint (let's call it zero_or_minusone) that assigns 0 to candidates whose counter 1 is empty, and -1 to candidates whose counter 1 has a positive integer value. Finally, adding the constant constraint "1" to zero_or_minusone will produce the constraint we need: *EmptyCounter.

Here is an OTKit script that produces it:

add2MyUniverse( Constraint("C", "Counter1" , "Value of counter 1." ))
add2MyUniverse( Constraint("minusC", "P1_*_Constr_P2" , "-1" , "C" , "-1 times constraint 'C'"))
add2MyUniverse( Constraint("minus1", "Constant_P1" , "-1" , "Assign -1 to any candidate."))
add2MyUniverse( Constraint("minusC_max_minus1", "Constr_P1_max_Constr_P2" , "minusC" , "minus1" , "Max of constraints 'minusC' and 'minus1': assigns either 0 (if C assigns 0) or -1 (if C assigns a positive integer)."))
add2MyUniverse( Constraint("1", "Constant_P1" , "1" , "Assign 1 violation mark to any candidate."))
add2MyUniverse( Constraint("*EmptyCounter", "Constr_P1_+_Constr_P2" , "minusC_max_minus1" , "1" , "Sum of constraints 'minusC_max_minus1' and '1': assigns either 1 (if C assigns 0) or 0 (if C assigns a positive integer)."))

The following "tableau" explains what is going on:

Candidate C minusC minusC_max_minus1 *EmptyCounter
counter = 00001
counter = 11-1-10
counter = 22-2-10
counter = 33-3-10
counter = nn-n-10

Note that this solution is probably not very efficient: it will slow down long experiments, because it takes too much time to evaluate a certain candidate. Therefore, if you program in Java, you can write your own class and import it to OTKit. Or ask me to do it for you. Or ask me to include such a constraint in the next version of OTKit. Please, do not be shy: probably there are constraints that are widely used, and only by receiving such requests do I know what the community of linguists really needs.

Exercise 1: Solve the same problem by using the conditional constraint scheme P1_:_pos_P2_zero_P3_neg_P4, within the "constraint arithmetic" type.

Exercise 2: create the constraint EmptyCounter, which is satisfied only if the counter is empty (zero violation marks), and which assigns one violation mark otherwise. You can either use constraint *EmptyCounter, which we have just created; or start from scratch to obtain a shorter (and faster to compute) solution.


6. Running OTKit from command line

As explained in the introduction, the program OTKit.jar can be run from command line. If your operating system or the file type association does not support simply clicking on the icon of the jar file, you have to launch the graphical user interface from command line:

java -jar OTKit.jar

If this command line does not help, then you should consult an expert how to install JRE 6 on your machine, or where to locate it. If it works, you can use the program from command line, without launching the graphical interface, and executing (probably more efficiently) scripts that take a long time to run. Here is an example for Linux that loads a universe file, then executes a script, saves the standard error and output to files, and does it in the background, so that you can even log out:

java -jar OTKit.jar -l universe.xml -s script.txt > out 2> err &

To get more help on command line options, enter:

java -jar OTKit.jar -h


7. Scripting language

Type help(script) to the bottom line of the OTKit main window, or the -S option in command line, to get an up-to-date list of commands available in the scripting language. The script command help(schemes) might also turn to be useful: it lists all the available schemes.

OTKit makes the difference between commands and expressions. The "return value" of a command is (if any) some output text: on the standard output, if the script has been launched from command line, and in the main window (dialogue panel) if the script has been launched from within the graphical user interface. Commands often correspond to buttons in pop-up windows of the graphical user interface. In contrast, the return value of an expression is an element: either a newly built one, or an element retrieved from MyUniverse based on its name.


help() Returns basic help.
exit() Quits OTKit.
print(t) Prints text t to the output.
history() Prints history of commands.
include(f) Executes the content of script file f at this point. Here f is a filename (optionally with path).
universe() Prints everything that is in MyUniverse.
add2MyUniverse(e1,..., en) Adds e1,... and en to MyUniverse, where e1,..., en are expressions (see below).
remove_from_MyUniverse(e1,..., en) Remove expressions e1,... and en from MyUniverse.
clear_MyUniverse() Make MyUniverse empty.
load(f) Loads the content of XML file f to MyUniverse. Here f is a filename (optionally with path) or a url.
load(f, e1,..., en) Loads elements/expressions e1, ..., en from XML file (or url) f to MyUniverse. Elements in f whose name coincides with the name of e1,... or en will be loaded.
save(f) Saves MyUniverse to file f, where f is a filename (optionally with path; in Windows, use / or \\).
save(f, e1,..., en) Saves elements/expressions e1, ..., en to file f, where f is a filename (optionally with path).
value(con, cand) Applies constraint con to candidate can.
grammatical_outputs(u, g, h) Generates the grammatical output[s] (candidate[s]) corresponding to underlying form u, Gen function g and hierarchy h.
grammatical_outputs(u, g, h, n) Generates the grammatical output[s] (candidate[s]) corresponding to underlying form u, Gen function g and hierarchy h. At most the first n elements of the candidate set are considered.
draw_tableau(u, g, h) Generates the tableau corresponding to underlying form u, Gen function g and hierarchy h.
draw_tableau(u, g, h, n) Generates the tableau corresponding to underlying form u, Gen function g and hierarchy h. At most the first n elements of the candidate set are considered.
is_grammatical(c, g, h) Check if candidate c is grammatical (most harmonic) with respect to Gen function g and hierarchy h.
is_grammatical(c, g, h, n) Check if candidate c is grammatical (most harmonic) with respect to Gen function g and hierarchy h. At most the first n elements of the candidate set are considered.


Candidate(n) Candidate in MyUniverse whose name is n.
Candidate(n, s, p1,..., pn) Create a new candidate whose name will be n, and whose scheme is s (check the spelling!). The number of parameters p1,..., pn is defined by the scheme.
Cand(str) Candidate with both name and surface form being string str (underlying form is empty form).
Constraint(n) Constraint in MyUniverse whose name is n.
Constraint(n, s, p1,..., pn, sd, ld) Create a new constraint whose name will be n, and whose scheme is s (check the spelling!). The number of parameters p1,..., pn is defined by the scheme. Long description ld is optional, as is short description sd (unless long description is specified).
Form(n) Form in MyUniverse whose name is n.
Form(n, s, p1,..., pn) Create a new form whose name will be n, and whose scheme is s (check the spelling!). The number of parameters p1,..., pn is defined by the scheme.
Hierarchy(n) Hierarchy in MyUniverse whose name is n.
Gen(n) Gen in MyUniverse whose name is n.
Gen(n, s, p1,..., pn) Create a new Gen whose name will be n, and whose scheme is s (check the spelling!). The number of parameters p1,..., pn is defined by the scheme.
Table(n) Table in MyUniverse whose name is n.
Table(n, r, c, (x11,...,x1c), (x21,...,x2c),...(xr1,...,xrc)) Create a table with name n. Number of rows is r, number of columns is c. Value of each row is put in parenthesis. If there are too few rows, or too few cells in a row, the rest is filled in with empty strings.

Everything after a # in a line is a comment. Note that currently a command must not contain an end-of-line character: one line must correspond to one command.

Example scripts are available here.


8. XML format

Elements (forms, candidates, constraints, hierarchies...) created by OTKit, as well as whole universes can be saved. The format used is an XML document, with a root element "universe", and nodes corresponding to the element types. The information needed to reconstruct the element (scheme and parameter values, or constraints and ranking variables, or table rows and cells) is encoded as attributes or subnodes. Additionally, each element also has an attribute "name" for its name in the universe. The DTD can be found here.

In the near future I also plan to allow you to create your own candidates, constraints, Gen functions, etc., beyond the schemes already incorporated in OTKit. This should mean that you can write Java classes, and there will be a scheme for every element type (constraint, candidate, etc.) whose parameter is your own class. This way, OTKit will be more flexible (at least for those with some Java knowledge; or for those with friends with some Java knowledge).


9. Java library

The OTKit project also includes a Java library which you can use to code your own Java programs. The latest version can be downloaded from the website. Earlier versions are also available here.

The Javadoc documentation of the library can be found at http://www.birot.hu/OTKit/doc/. Please report any inconsistency, errors, typos or missing descriptions in the Javadoc: I'm sure you know how a software documentation comes into being...


10. Concluding remarks

Bug reports and comments

Please report all bugs and other comments to the author of this software, Tamás Biró (OTKit [at] birot . hu).

Acknowledgments and historical notes

I developed the SA-OT demo page, a PHP-based implementation of the SA-OT Algorithm in 2005, while I was working on my doctoral dissertation at the University of Groningen (RUG). That is when it became clear that a more flexible implementation of OT is needed, allowing for an infinite candidate set, defining a topology as a regular expression, having constraints applicable to any string without having to list all its domain, and so on. After all, the main point about SA-OT – similarly to some other, non-trivial implementations of OT – was that it is an algorithm able to find the best candidate (with some probability) without having to list all of them, even in an infinite candidate set.

Then, I understood the advantages of using Java during my appointment in the TDS project at the University of Amsterdam. Version 0.0.epsilon of OTKit (called SimpleOT at that time) was developed while I worked for ALL. The actual development started at the University of Groningen, where students of my research seminar also had to write their own implementation of Optimality Theory. Version 1.0 has been accomplished as part of a Netherlands Organisation for Scientific Research grant (NWO, project number 275-89-004) at the University of Amsterdam. The list of people whose useful feedback has improved OTKit started with Bart de Boer and Menzo Windhouwer, and hopefully will become much longer. Thank you very much!

The software uses a number of solutions copy-pasted from the web. I am thankful to the authors of all the examples posted in discussion forums, course websites, etc.