Calculating Semantic Similarity between Academic Articles using Topic Event and Ontology

Determining semantic similarity between academic documents is crucial to many tasks such as plagiarism detection, automatic technical survey and semantic search. Current studies mostly focus on semantic similarity between concepts, sentences and short text fragments. However, document-level semantic matching is still based on statistical information in surface level, neglecting article structures and global semantic meanings, which may cause the deviation in document understanding. In this paper, we focus on the document-level semantic similarity issue for academic literatures with a novel method. We represent academic articles with topic events that utilize multiple information profiles, such as research purposes, methodologies and domains to integrally describe the research work, and calculate the similarity between topic events based on the domain ontology to acquire the semantic similarity between articles. Experiments show that our approach achieves significant performance compared to state-of-the-art methods.

Introduction
Text semantics matching is widely used in many applications such as machine translation, automatic question answering, and knowledge retrieval. It also has great significance in plagiarism detection, automatic technical survey, citation recommendation and research trend analysis in academic domain. The issue of text semantics, such as word semantics and sentence semantics has received increasing attentions in recent years. However, rare research focuses on the document-level semantic matching due to its complexity. Long documents usually have sophisticated structure and massive information, which causes hardship to measure their semantic similarity, and there is even no public available dataset as far as we know.
Large text units are composed of small text units. The semantics of long document can be derived from the combination of small text unit semantics. Many recent studies follow this thought to acquire the semantic similarity between larger text units. For example, the sentence semantic similarity can be achieved from the integration of semantic similarities between word pairs from two sentences [1,2]. Besides lexical semantics, global sentence level features are also considered for acquiring the semantic similarity between sentence [1][2][3][4][5][6][7][8]. However, those studies only focus on short texts by lexical semantics and sentence-level features, which are still far from the capability of document-level semantic similarity.
The study focusing on semantic similarity between documents is relatively rare. Existing methods of document-level similarity mainly focus on information retrieval in surface level rather than semantic level understanding. Those conventional similarity metrics [9][10][11] measure the document similarity by statistics or morphology of words, neglecting documents' structure and meanings of their words, such as vector space model (VSM) [12]. VSM regards each document as a collection of words and measures the document similarity mainly based on the presence of words, e.g., there are two snippets of text: "Jack borrowed a book from the teacher" and "The teacher borrowed a book from Jack". VSM regards the two texts as equal, but actually they have opposite meanings. Latent Dirichlet Allocation (LDA) [13] is proposed for the deep analysis of documents based on the difference of topic distributions over documents, which can be used to measure document-level semantics. There are also researches [14][15][16][17][18][19] trying to add external knowledge to the document representation, which enrich the content by adding the relevant terms from knowledge resources. However, these methods still suffer from problems like computational complexity and representational opaqueness.
Long documents contain many topic transitions and different focuses, which makes it difficult to capture their core semantics. However, we believe that those topics in a document are coherent, and those correlations can be obtained by the comprehensive analysis on various factors of a document. Hence, we represent the core semantic issue in each document as an event which is called a Topic Event (TE). TE is the structured summary extracted from each document, which contains the comprehensive key elements of the document.  The core semantics of an academic article is the authors' research work. We construct TE based on the article structure and using multiple information fields such as research targets, methodologies, keywords and domains, which can integrally describe various facets of the research work. Hence, the semantic similarity between academic papers can be measured by TE similarity, which is shown in Fig. 1. For achieving high accuracy in TE similarity calculating, we also develop and utilize the research style ontology and domain ontology in the academic domain. In order to make our approach more practicable, we present the method of how to automatically construct a TE. To verify performances, we construct an evaluation corpora by manual annotation using ACL Anthology Network (AAN) corpora [20]. Experiments demonstrate that our methods gain outstanding performance, and the results are also more conforming to human's comprehensions. To summarize, the main contributions of our work are as follows: -We propose the idea of constructing the topic events as the semantic representations of long documents, and give a general method for topic event similarity calculation.
-We develop and construct the research style ontology and the domain ontology for academic articles, and these two knowledge resources can facilitate the semantic extraction and similarity measurement procedures of the topic event effectively.
-We provide an ontology-based automatic TE construction method without labeled data in a specific domain, and utilize this method in the topic events construction of computational linguistic documents.
-We introduce a document semantic matching corpus with fine-grained annotations for the first time, which can serve as the ground truth for the evaluation of document-level semantic matching researches.
The remainder of the paper is organized as follows. In Section 2, we describe the related work. Section 3 provides the sketch of the topic event in academic domain. In Section 4, an automatic construction method of topic event is given. In Section 5, we describe the similarity computing method of the topic event. In section 6, the domain ontology and evaluation corpora in the computational linguistics domain are constructed, and then the experimental evaluations are given. Finally, we conclude the paper in Section 7.

Related work
The document-level semantic similarity research is a new arising area, which is thought can be enlightened by the concept and short text semantic matching methods. The concept-level semantics is the bricks of document semantic comprehension, and the short text-level similarity is the current most active area, which throws light on the document-level semantic similarity. In general, concept-level semantic similarity can be measured by knowledge-based methods and corpus-based methods. Knowledge-based methods mainly utilize the path between concepts in knowledge resources to indicate their semantic similarity [21,22]. Lin [23] and Resnik [24] measured the semantic similarity by the information content ratio of the least common subsumer of the two concepts. Instead of directly exploiting the graph distance in knowledge resources, several researches [25,26] manufactured concept vectors according to a set of ontology properties for concept semantic similarity. Corpus-based methods assume that words with similar meaning often occur in similar contexts, Latent Semantic Analysis (LSA) [27] represents words as compact vectors via singular value decomposition (SVD) on the corpus matrix, and GloVe [28] reduced computational costs by training directly on the non-zero elements in corpus matrix. Turney [29] measured semantic similarity with the point-wise mutual information. Web can also be regarded as a large corpus, and the Google Distance [30] utilizes the number of words co-occur in web pages for concept semantic similarity. Mikolov [31] proposed the word embedding approach with neural network to capture the word semantics occurred in a fixed size window.
A challenge for determining semantic similarity of short texts is how to go from word-level semantics to short-text-level semantics. A direct approach is utilizing weighted sum of word-toword semantic similarity, and [1,2] used the greedy word alignment method to form the sentence semantic similarity. Banea et al. [3] measured the semantic similarity between text snippets infused with opinion knowledge. D Ramage et al. [6] constructed a concept graph using words of each text snippet, then measured the similarity between two concept graphs. Recently, the SemEval conference released the Semantic Text Similarity (STS) task especially for the boom of short text semantics, and regression models are adopted by most teams [5,8] to predict the similarity score, and lexical feature and syntactic features are exploited. The paragraph vector [32], which is similar to word embedding, is also proposed with neural network to measure the semantic similarity between short texts.
The research directly related to document semantic similarity is rare and undeveloped. Traditional similarity researches such as the TF-IDF [12] converted documents to vectors via word counting, and measured the similarity between documents by the similarity of vectors. Academic articles can be regarded as semi-structured texts, which contain many structured annotations besides plain text. The similarity between academic articles can be measured with the help of annotated information. Martin et al. [33] fused the structured information, such as authors and keywords with traditional text-based measures for academic articles similarity. [9][10][11] regard articles and their citations as an information network. The similarity between articles turns to the similarity of two entities in information network. Unfortunately, the above conventional similarity methods aim at document indexing in surface level, rather than semantic level document understanding.
There are several studies trying to add external knowledge to achieve the semantic representation of documents. [14,15,17] enriched the content by adding relevant terms from knowledge resources, which aim at improving the quality of the document clustering results. [18,19] extracted relation triples from source document and added entity relations from background knowledge to construct triple graph for document enrichment. Schuhmacher and PonzeRo [16] proposed a graph-based semantic model for representing document content, which added knowledge to the document representation by linking the entities in the document to the DBpedia knowledge base. Those methods acquire fine-grained relationships among entities and generate a knowledge-rich document model, and the semantic similarity is calculated by the graph edit distance. However, above methods are lack of interpretation. Furthermore, there are rare entities such as persons, organizations and place names inside the content of academic articles, which makes those methods unsuited.
Long documents such as academic articles usually have several focuses and vast amount of words. LDA [13] obtains the semantic relatedness among different concepts via topics and regards each document as a distribution over a set of topics. Thus LDA can be used in the semantic analysis of long documents. Muhammad Rafi [17] defined a similarity measure based on topic maps in the document clustering task. The documents are transformed into topic maps based coded knowledge, and the similarity between a pair of documents is represented as a correlation between their common patterns. M. Zhang et al. [34] enriched document with hidden topics from external corpora, and measured the document similarity in text classification task with the similarity of topic distributions. Along the direction of topic model, [35,36] measured the semantic similarity between documents based on the divergence of topic distributions, which can be calculated by the Kullback-Leibler (KL) distance, and the LDA-based method is befitting in the semantic similarity task between academic articles.

Topic event
What can be used to convey the main semantics of a long document? The task is complicated and would not benefit directly from the simple accumulation of massive concept semantics. To get a global comprehension of a document, it's necessary to extract key information from large amount of words and form a core semantic of a document.

Topic event structure
In academic domain, articles are used to convey the research progress. Most academic articles have normative formats and regular structures, and the research work comprises similar profiles, which can be described in a uniform topic event structure.
The most notable points of an academic paper are their purposes, methods and results, which convey the main information of the research work. Keywords can fuzzily represent the core semantics and acquaint readers with the general research cognition. The domain of research issues indicates the research branch, and the type of research work reflects the research style and difficulty. The publication dates imply different stages of research issues. We define the above factors as the primary elements in a topic event, and the structure of the topic event is defined in Fig. 2.
The items annotated with * is crucial and essential, which cannot be vacant, while other items are optional. Eid and Did are essential identifications for topic event and the corresponding paper. Style indicates the research type, and the elements such as Domain, Target, Methodology, keywords are terminologies extracted from papers, while the elements of Conclusion, Background, Performance and Forecast are key sentences in papers.

Research style ontology
The styles of research work implicate important semantics. They can reflect the variance of researches in difficulties, ways and types. For example, E1 and E2 are two research work as follows.
E1: The authors survey the techniques around a certain issue and summarize them as an academic article.
E2: The authors focus on a certain problem and propose a solution, the process and result of the solution are written as an academic paper. There are distinct differences between E1 and E2. E1 is a paper of Survey class, while E2 is a paper of Issue Solution class. In general, E2 has more innovation and difficulty than E1, and they have different values. E1 is suitable for beginners to get basic knowledge, while E2 is more suitable for inspiring experienced persons. Therefore, the type of an academic paper is an important factor in expressing its semantics. To express the knowledge implicated by types of research styles, we first develop the style categories of topic event, which is constructed in Fig.  3 by using proté gé [37]. Each definite style of each research work is shown and explained in Table 1. The research style ontology implicates the relations between different styles of research work, which can be used to measure the semantics between different academic researches.

Overview
As shown in Figure 2, we need to extract the Target, Methodology, Domain, Style, Keywords and Date from a document to construct the topic event. Present work on extracting structured representations of events has focused mainly on newswire texts, which utilize labeled entities, time expressions and values occurred in target sentences as candidate event items. The traditional event extraction problem is regarded as a classification problem with the help of labeled data. However, there is rare labeled data for training an extraction model, and almost no labeled entity can serve as the candidate terminologies in a specific domain.
Academic literatures have several characteristics which present unique challenges and opportunities for event item recognition. There are many structured annotations in academic articles such as the citations, authors, date of publication, keywords and journals, which are obvious to extract and can be used to enrich the topic event [38]. Notwithstanding, many important items of topic event are hidden in the unstructured content of academic articles. The main work of extraction is to identify terminologies such as target, methodology, domain and style in the article content. To solve the problem of lacking labeled event data, we propose an ontology and pattern-based extraction method.
Academic articles usually have clear topics and purposes, and there are many regular syntactical structures in academic articles which give clues to event extraction. The process of topic event construction is described in Fig. 4. Firstly, we divide the academic articles into different sections and select the most significant sections for topic event extraction. Then we conduct basic natural language processing (NLP) such as sentence splitting and part-of-speech (POS) tagging on each implicated sentence in the selected sections. Thirdly, we choose all the noun phrases (NP) in each sentence as candidate topic event items as well as a limited terminology list derived from the domain ontology. After that, the best event arguments are chosen from several candidates after pattern matching. At last, the extracted event items are delivered to the domain ontology to expand the related event semantic items. Generally, the domain ontology conveys the semantic relatedness among domain terminologies, which can provide the terminologies as well as their relationships in a specific domain. In this paper, the domain ontology can provide extern knowledge for the semantic comprehension of documents, and assist the procedure of topic event construction.

Event items recognition
In detail, we divide each academic article into several chunks according to its outline, and the Title, Abstract, Introduction and Conclusion sections are believed to have a global description of the whole research work without much unnecessary detail. Then we identify the implicated sentences from above sections by trigger words. The implicated sentences may contain the event items, and we define a total of 95 trigger words for items extraction.
To capture the candidates of event items in implicated sentences, we leverage the domain ontology and some NLP processes. A terminology list derived from the domain ontology is used to find potential event items. However, another key issue is how to find a lot of unknown phrases in novel academic articles. To solve this problem, we conduct POS tagging on each sentence, and then utilize all the noun phrases as the candidates of event items to capture the unknown new phrases.

Recognition of target and methodology
After acquiring the candidate terminology, the next step is to confirm which candidate is the best event item in each sentence. We develop the patterns for the extraction of Target, and Methodology. The extracting patterns are composed of pre-patterns and post-patterns, which are the patterns occurs frequently ahead of the event items and the patterns occurs frequently after the event items. Several typical extracting patterns of Target and methodology are shown in Table 2. There are altogether over 550 patterns for the extraction of Target and Methodology.
For example, the implicated sentence "In this paper, we propose a supervised machine learning approach for relation extraction" is identified by the trigger words "propose" from the introduction section of an academic article. It matches the preceding target pattern, i.e. "approach for". Thus, the terminology "relation extraction" is chosen as the target of this article.  linguistic domain can be diagnosed by the title of the paper. For example, each title of Issue Solution type is distinct, it will start with the abbreviated name of their software and connect the succeeding title with the punctuation ":" or "-", e.g., "TEXTRUNNER : Open Information Extraction On the Web", "URES : An Unsupervised Web Relation Extraction System". Most titles have featured words to distinguish their research styles, and we develop patterns to identify the topic research style in Table 3.

Ontology-based semantic expansion
Many items in a topic event are closely correlated such as the research purpose and domain, the adopted methodology and toolkit, the research object and dataset. Generally, the research purposes are the core issues of the academic articles and corresponding topic events, and the domain that an academic article belongs to is decided by its research purpose. When we extract the target of an academic article, we use the domain ontology to induct which domain it belongs to.

General framework
Since topic event can represent the semantics of a document, the semantic similarity between documents can be achieved via the similarity between topic events. In this paper, we get the information hidden in each document via the topic event, and acquire the internal relevance among concepts from the domain ontology.
In our method, to compute the core semantics of papers in brief, six primary elements in topic event are employed according to their characteristics, which are Target, Domain, Style, Methodology, Keywords and Date. We use topic event ontology to measure the internal event similarity between different types, and the domain ontology is used to measure the internal semantic similarity between terminologies. We measure topic event similarity by the weighted sum of element similarities in corresponding event structure, and it also can be extended by metadata and other elements for a more detailed topic event similarity. Similarity between topic events E1 and E2 is defined in equation (1): where wi is the weight of the ith element in the topic event, Si is the similarity function between the ith elements of L1 and L2. L1 and L2 are two topic events whose elements are defined as L= {Target, Domain, Style, Methodology, Keywords, Date}.
The topic events extract the core semantics of each academic articles. However, the meaning of event items could not be measured by their literal appearance. Background knowledge such as lexical meaning is necessary to comprehend the semantics of articles. To get the internal semantic relatedness among different terminologies, the terminologies in topic events should be linked to the concept nodes in knowledge bases to obtain their semantic relatedness. In the following section, we will introduce the concept linking method and the measurement of item semantic similarity.

Domain ontology concept linking
To calculate the internal similarity between terminologies, an important issue is to link the extracted terminologies to proper positions in the knowledge base. There are many synonyms in academic articles, and many concepts may be described by different terminologies in different papers such as "cross linguistic retrieval" and "multilingual information retrieval", "text understanding" and "message understanding", "named entity recognition" and "named entity tagger". When we construct the domain ontology, we labeled all the known synonyms of each concept in the node to facilitate entity linking.
Many automatically extracted terminologies wear trivial suffix and prefix, which may hinder the entity linking. To solve this problem, we use the edit distance to measure the string similarity and recognize the variations of the same concept. Since our ontology are constructed for the computational linguistics domain, and all of the concepts nodes are extracted from domain corpus, most terminologies will find the extract concept position in the domain ontology. We first derive a terminology list to form the domain ontology. When a terminology extracted from the academic articles comes, its edit distance with each of the terminology are calculated. The concept node with minimum edit distance will be regarded as the terminology node.

Item similarity of topic event
The items such as Target, Methodology and Domain are terminologies, and their semantic similarities can be measured by the domain ontology. The semantic similarity between Style can be measured via the research style ontology. The Date similarity can be measured by their interval. In brief, the similarity of those items in topic events can be measured by the following methods.
Research Style Similarity To measure the difference between different types of research work, the research style ontology described in Table 1 can be used. The Style similarity between different types of topic events is measured similar to Wu and Palmer method [22] based on the research style ontology shown in Fig. 3, and the formula is as equation (2): where Style1 and Style2 means the types of two topic events. LCS is the least common subsumer of two style nodes. Terminology Similarity Concept semantic similarity can be measured by knowledgebase. We evaluated several knowledge-based methods and found Wu and Plamer [22] method is suitable for the concept similarity in this domain. The contents of target, Domain, Methodology and Keywords are collections of terminologies, which can be measured by Wu and Palmer method based on the domain ontology or word embedding-based methods. The ontology-based concept semantic similarity is measured by equation (3): where ec1 and ec2 represent terminologies in the topic event.
When the corpus-based concept similarity method is used for terminology semantic similarity, the cosine similarity between terminology vectors can be used. The cosine similarity is defined in equation (4): Date Similarity Research issues keep evolving along time, and researchers will focus on different scientific issues in each period. We assume that the academic articles that have close date will be more similar, and the academic articles published far from each other will have less common points. Thus, date similarity can be measured by the time interval. Years and months are used to compute the similarity between two dates. We define the Date Similarity formula is as equation (5) .

Corpora construction
There are several public datasets used to evaluate the semantic similarity of short texts and sentences, such as MSPR [3], Michael D.LEE 50 corpus [7] and SEMILAR corpus [5]. However, no text of those datasets is more than 200 words, which could not validate the document-level semantic similarity. Hence, we construct the semantic similarity dataset between documents using the academic papers in computational linguistics domain. A set of paper pairs are generated from AAN corpus [20]. The paper pairs are annotated by both a 2-level and by a 5level annotation as ground truth. Each paper pair is marked as 1 if semantically similar or 0 if dissimilar in 2-level annotation. In 5-level annotation a paper pair is marked by integers ranging from 1 to 5 according to their semantic similarity degree. If they are totally equal in semantic, similarity between papers will be annotated as 5, and if they have nothing to do with each other, similarity is annotated as 1. Twelve experts from our lab annotated and cross validated the coherence of 1021 pairs of documents. Each paper pair get a second annotation by a different person after the first annotation. If the second annotation is in accordance with the first one, it will be annotated as the ground truth, else a third person will annotate the paper pair to get the ground truth. In the end we got an annotated corpus with 1021 paper pairs. Now the corpus is public, and the url is: https://github.com/buaaliuming/DSAP-document-semantics-foracademic-papers/tree/buaaliuming-annotation .

Computational linguistics ontology
Common knowledge resources such as WordNet couldn't cover domain terminologies. In order to compute semantic similarity between terminologies, we manually construct the domain ontology to convey the semantics among different terminologies.   The Concepts extracted from AAN corpus [20] are used to manually construct a computational linguistics ontology. Currently our ontology includes 1195 concept nodes with a hierarchy of 9 depths, which will be expanded persistently in future. The Computational Linguistics Ontology (CL Ontology) architecture is shown in Fig. 6. The main relationships between concepts in the ontology are hyponymy. Synonyms are considered and annotated in the ontology concept nodes during the construction.
CL ontology is used to measure the similarity between computational linguistic domain concepts. According to the characteristic of computational linguistic domain, we design the ontology as three parts, they are: Research Topic, Infrastructure and General Approaches, and each part is enriched by more detailed descendant nodes. The node General Approach includes common methodologies used in computational linguistics, such as machine learning, pattern matching and knowledge engineering, etc. The node Research Topic includes fundamental language processes, research issues and research objects. Fundamental language process includes natural language processing, such as word segmentation, syntactic parsing, POS tagging, lemmatization, etc. Research issues include research hotspots such as machine translation, text category, information extraction, information retrieval and speech recognition, etc. The node Infrastructures contains the general toolkits, knowledge bases, corpora, and organizations in the field of computational linguistics.

Experimental setup
The experiments are conducted on the DELL OptiPlex390 machine, which has 8G memory and an I5-2400 CPU. Besides automatic constructed topic events, we also manually annotate the corresponding topic events of academic papers for experimental contrast. The LDA-based method is chosen as the baseline method. When computing the semantic similarity between terminologies in topic events, the LSA method is used as well as the ontology-based method. In brief, we conduct the following methods.
LDA_2013 The LDA-based method [36] in 2013 is the most related research and is chosen as the baseline method for contrast. When performing the LDA-based method, several LDA models with different parameters are trained based on the AAN corpus. In the following presented results, we choose the LDA model with 200 topics for contrast, which achieves the best performance among different LDA models under the same conditions.
TE_Onto the TE semantic similarity method are conducted on the golden topic event annotations, and the concept semantic similarities are computed by our CL ontology.
AutoTE_Onto the TE semantic similarity method are conducted on the automatic extracted topic events, and the concept semantic similarities are also computed by our CL ontology. The AutoTE_Onto method is used as the comparison of TE_Onto method to measure the influence of automatic topic event extraction.
TE_LSA the TE semantic similarity method are conducted on the golden topic event annotations, and the concept semantic similarities are computed by the word vectors produced by LSA. The LSA method derives each word representation by SVD operation, and the semantic similarity between terminologies is captured by the similarity of the common topics. When the LSA method is used in the calculation of TE item, we constructed term-by-document matrix over the whole annotated corpus. The TE_LSA method is used as the comparison of the TE_Onto method to measure the effect of the Computational Linguistics Ontology.
AutoTE_LSA the TE semantic similarity method are conducted on the automatic extracted topic events, and the concept semantic similarities are also computed by the word vectors produced by LSA.
TE item weights The primary items of the topic event are Target, Domain, Methodology, Style, Keywords and Date, which are the essential items in Fig. 2. According to our experience, the research target is the crucial issue in each academic article. The research domains, types of research work and adopted methods in academic articles are important aspects, which are discriminative characteristics of each research work. While the keywords are a set of fuzzy description lack of definite semantics. The dates of publication imply the different ages of technology, which are less discriminative and not directly related to various research work. We set the weight of aforementioned items according to their importance, and in our experiments, weights of the items, i.e. Target In this work, X is the predicted semantic similarity score, and Y indicates the annotated semantic similarity value. The ( , ) represents the covariance of X and Y. The and represent mean values of the variables X and Y; and are standard deviations of X and Y respectively.
Since our corpus has both binary annotations and five-level annotations, we further set different thresholds to predict whether two documents are semantic similar. Both the Accuracy and F1-score can be the overall evaluation metric beside correlation. The Accuracy is shown it equation (7).
In equation (7), TP means the number of document pairs predicted to be similar that actually are similar document pairs. TN means the number of document pairs predicted to be dissimilar that actually are dissimilar. FP is the number of document pairs predicted to be similar that are actually dissimilar FN is the number of document pairs predicted to be dissimilar that are actually similar.
Accuracy means the general predict ability of a method, and F-score means the comprehensive performance of precision and recall. The F-score is shown it equation (8).
The P means Precision and the R means Recall. In general, the value of β is 1, and the F score is annotated as F1-score in the following section.

Pearson correlation
To verify the quality of different methods, we calculate the Pearson's correlations of 1021 similarity scores with the human annotated ground truth.
Comparison with the baseline The results in Table 4 show that our ontology-based TE method has distinct advantage on the baseline method, i.e. LDA_2013. The 5-level annotation has more detailed similarity levels; and the correlation scores with it are more convincing than the 2-level correlation scores. Our TE_Onto method achieves 4.1% (relative) improvement over the baseline method; when the topic events are extracted automatically, our AutoTE_Onto method can gain 5.8% (relative) improvement over the baseline method. The impact of ontology Our TE_Onto method performs much better than the LSA-based TE method ， and the AutoTE_Onto even shows 22.7% advantage over the AutoTE_LSA method when topic events are extracted automatically.
The LSA-based method measures the semantic similarity of concepts by common word topics or word co-occurrence, while the ontology-based methods measure the concept semantic similarity via accurate knowledge in ontology. Above results show that the knowledge resource such as the domain ontology are of great importance in the measurement of document semantics.
The impact of TE extraction The correlation scores of our methods on automatic constructed topic events and human annotated topic events are close. The performance of our methods with automatic extracted topic events is comparable to the golden topic events annotated by experts. The TE_LSA method only shows minor advantage on the AutoTE_LSA method, and the AutoTE_Onto method even performs little better than the TE_Onto method in 5-level annotation correlation. This shows that, the pattern-based extracting method can extract necessary information with proper precision in a specific domain, and the process of automatic extraction produces comparable performance to human annotation.

Accuracy and F1-score
Accuracy and F1-score can be the general evaluation metrics beside Correlation. The Accuracy indicates the general capability of a method to predict the right result; the F1-score is a balance of precision and recall, which indicates the comprehensive capacity of the method. In practical applications, different thresholds can be set to predict whether two documents are semantic matching. Generally, the best performance among different thresholds is considered as an important factor in evaluation. In the following experiments, different thresholds are set. Paper pairs are thought semantically similar if their similar score is greater than the given thresholds.
Comparison with the baseline As shown in Fig. 7 and Fig. 8, the Accuracy of our TE methods always has distinct advantage over the LDA_based method at different thresholds.
Our best F1-score is 0.639, while the best F1-score of the baseline method is 0.536. The F1score of our AutoTE_Onto method outperforms the LDA_2013 at most thresholds, and the F1scores of our TE_Onto methods with golden topic event show advantage over the baseline method when the threshold is less than 0.75.  The impact of ontology We compare the performance of LSA-based TE method and the Ontology-based TE method. As shown in Fig. 9 and Fig. 10, the best Accuracy of LSA-based TE method is 0.712, while the best Accuracy of Ontology-based TE method is 0.768. The Ontology-based TE methods perform much better than the LSA-based TE methods when thresholds are more than 0.250. To sum up, the ontology-based TE methods perform better than LSA-based TE methods, which is in accordance with the result of the Pearson Correlation in the last subsection. Those results show that the ontology plays a crucial role in the document semantic similarity. Discussion Above experiments demonstrate that TE methods can yield much better performance in general. The similarity scores of TE_LSA method and AutoTE_LSA method range from 0.0 to 0.70, and there is no true positive result when the thresholds are above 0.70. Those low level similarity scores make the F1-scores of LSA-based TE method incalculable. Academic articles usually have long contents containing lots of duplicate terminologies, and the frequent terminologies in a specific domain trend to occur in many domain articles. Besides, academic papers tend to review related work. The LDA-based method determines the topic similarity by the word overlap. Hence, the similarity scores of LDA_2013 ranges relatively high from 0.7 to 1.0, which makes it perform good in recall but poor in precision, and depress its overall performance. Our methods hold the core semantics of a document directly via structured topic event, the similarity scores of TE methods fluctuate from 0.0 to 1.0 according the similarity of document pairs, and they are more discriminative and have better overall performance.

Time and memory cost
Each method in our experiment needs an off-line process. It's hard to measure and compare the off-line process of those costs in different environments and procedures. In this section we measure the running time when computing the document-level semantic similarity under the same condition. The average consuming time of TE methods is 0.002s and the memory occupation is about 100M, while the LDA_2013 costs 4.83s and occupies more than 8G memories. It's obvious that our TE methods are more efficient than the traditional LDA-based measurement in time and memory cost. The reason is that our TE methods utilize a domain ontology to calculate the semantic similarity rather than a large LDA model. In general, our TE Methods that achieve semantic similarities based on extraction and template get desirable overall performance.

Conclusions
This paper proposes for the first time constructing a topic event to represent the semantics of a document and measures the semantic similarity between the academic literatures by computing the similarity of their corresponding topic events. We define the general architecture of topic event and give the construction and similarity computing methods of topic events. The research style ontology and an evaluation corpus are constructed. To measure the concept semantic similarity, we design the Computational Linguistics Ontology. The evaluation experiments show that our topic event method gets significantly improvement on current semantic similarity measurements, and the ontology-based TE methods show overall advantages in Correlation, Accuracy and F1-score. The knowledge resources such as the domain ontology play a crucial role in the document semantic similarity.
Furthermore, our method can be used for modeling the semantics of different styles of research work, and the ontology-based automatic construction and similarity calculation of TE are concordant across different domains, which means our method could be easily utilized in various academic domains.


IJCNLP-2017 Task 2: Dimensional Sentiment Analysis for Chinese Phrases

This paper presents the IJCNLP 2017 shared task on Dimensional Sentiment Analysis for Chinese Phrases (DSAP) which seeks to identify a real-value sentiment score of Chinese single words and multi-word phrases in the both valence and arousal dimensions. Valence represents the degree of pleasant and unpleasant (or positive and negative) feelings, and arousal represents the degree of excitement and calm. Of the 19 teams registered for this shared task for two-dimensional sentiment analysis, 13 submitted results. We expected that this evaluation campaign could produce more advanced dimensional sentiment analysis techniques, especially for Chinese affective computing. All data sets with gold standards and scoring script are made publicly available to researchers.

Introduction
Sentiment analysis has emerged as a leading technique to automatically identify affective information within texts. In sentiment analysis, affective states are generally represented using either categorical or dimensional approaches (Calvo and Kim, 2013). The categorical approach represents affective states as several discrete classes (e.g., positive, negative, neutral), while the dimensional approach represents affective states as continuous numerical values on multiple dimensions, such as valence-arousal (VA) space (Russell, 1980), as shown in Fig. 1. The valence represents the degree of pleasant and unpleasant (or positive and negative) feelings, and the arousal represents the degree of excitement and calm. Based on this twodimensional representation, any affective state can be represented as a point in the VA coordinate plane by determining the degrees of valence and arousal of given words (Wei et al., 2011;Malandrakis et al., 2011; or texts (Kim et al., 2010;Paltoglou et al, 2013;Wang et al., 2016b). Dimensional sentiment analysis has emerged as a compelling topic for research with applications including antisocial behavior detection (Munezero et al., 2011), mood analysis (De Choudhury et al., 2012) and product review ranking (Ren and Nickerson, 2014) The IJCNLP 2017 features a shared task for dimensional sentiment analysis for Chinese words, providing an evaluation platform for the development and implementation of advanced techniques for affective computing. Sentiment lexicons with valence-arousal ratings are useful resources for the development of dimensional sentiment applications. Due to the limited availability of such VA lexicons, especially for Chinese, the objective of the task is to automatically acquire the valence-arousal ratings of Chinese affective words and phrases.
The rest of this paper is organized as follows. Section II describes the task in detail. Section III introduces the constructed datasets. Section IV proposes evaluation metrics. Section V reports the results of the participants' approaches. Conclusions are finally drawn in Section VI.

Task Description
This task seeks to evaluate the capability of systems for predicting dimensional sentiments of Chinese words and phrases. For a given word or phrase, participants were asked to provide a realvalued score from 1 to 9 for both the valence and arousal dimensions, respectively indicating the degree from most negative to most positive for valence, and from most calm to most excited for arousal. The input format is "term_id, term", and the output format is "term_id, valence_rating, arousal_rating". Below are the input/output formats of the example words "好" (good), "非常好" (very good), "滿意" (satisfy) and "不滿意" (not satisfy). with valence-arousal ratings. For multi-word phrases, we first selected a set of modifiers such as negators (e.g., not), degree adverbs (e.g., very) and modals (e.g., would). These modifiers were combined with the affective words in CVAW to form multi-word phrases. The frequency of each phrase was then retrieved from a large web-based corpus. Only phrases with a frequency greater than or equal to 3 were retained as candidates. To avoid several modifiers dominating the whole dataset, each modifier (or modifier combination) can have at most 50 phrases. In addition, the phrases were selected to maximize the balance between positive and negative words. Finally, a total of 3,000 phrases were collected by excluding unusual and semantically incomplete candidate phrases, of which 2,250 phrases were randomly selected as the training set according to the proportions of each modifier (or modifier combination) in the original set, and the remaining 750 phrases were used as the test set.
Test set: For single words, we selected 750 words that were not included in the CVAW 2.0 from NTUSD (Ku and Chen, 2007) using the same method presented in our previous task on Dimensional Sentiment Analysis for Chinese Words . Each single word in both training and test sets was annotated with valence-arousal ratings by five annotators and the average ratings were taken as ground truth. Each multi-word phrase was rated by at least 10 different annotators. Once the rating process was finished, a corpus clean up procedure was performed to remove outlier ratings that did not fall within the mean plus/minus 1.5 standard deviations. They were then excluded from the calculation of the average ratings for each phrase.
The policy of this shared task was implemented as is an open test. That is, in addition to the above official datasets, participating teams were allowed to use other publicly available data for system development, but such sources should be specified in the final technical report.

Evaluation Metrics
Prediction performance is evaluated by examining the difference between machine-predicted ratings and human-annotated ratings, in which valence and arousal are treated independently. The evaluation metrics include Mean Absolute Error (MAE) where Ai is the actual value, Pi is the predicted value, n is the number of test samples, A and P respectively denote the arithmetic mean of A and P, and σ is the standard deviation. The MAE measures the error rate and the PCC measures the linear correlation between the actual values and the predicted values. A lower MAE and a higher PCC indicate more accurate prediction performance.

Baseline
We implemented a baseline by training a linear regression model using word vectors as the only features. For single words, the regression was implemented by directly training word vectors to determine VA scores. Given a word wi, the baseline regression model is defined as where Valwi and Arowi respectively denote the valence and arousal ratings of wi. W and b respec-tively denote the weights and bias. For phrases, we first calculate the mean vector of the constituent words in the phrase, considering each modifier word can also obtain its word vector. Give a phrase pj, its representation can be obtained by,   (Mikolov et al., 2013a;2013b) (di-mensionality=300 and window size=5).

Results
Tables 2 shows the results of valence-arousal prediction for single words. The three best performing systems are summarized as follows. Tables 3 shows the results of valence-arousal prediction for multi-word phrases. The three best performing systems are summarized as follows.   Table 3: Comparative results of valence-arousal prediction for multi-word phrases. Table 4 shows the overall results for both single words and multi-word phrases. We rank the MAE and PCC independently and calculate the mean rank (average of MAE rank and PCC rank) for ordering system performance. The three best performing systems are THU_NGN, AL_I_NLP and CKIP. Table 5 summarizes the approaches for each participating system. CASIA, SAM and XMUT did not submit reports on their developed methods. Nearly all teams used word embeddings. The most commonly used word embeddings were word2vec (Mikolov et al., 2013a;2013b) and GloVe (Pennington et al., 2014). Others included FastText 4 (Bojanowski et al., 2017), characterenhanced word embedding (Chen et al., 2015) and Cw2vec (Cao et al., 2017). For machine learning algorithms, six teams used deep neural networks such as feed-forward neural network (CKIP), boosted neural network (BNN) (AL_I_NLP), convolutional neural network (CNN) (NLPSA), long short-term memory (LSTM) (NCTU-NTUT and THU_NGN) and ensembles (Mainiway AI and THU_NGN). Three teams used regressionbased methods such as support vector regression (CIAL, CKIP, LDCCNLP) and linear regression (CIAL). Other methods included a lexicon-based 4 https://github.com/facebookresearch/fastText

Conclusions
This study describes an overview of the IJCNLP 2017 shared task on dimensional sentiment analysis for Chinese phrases, including task design, data preparation, performance metrics, and evaluation results. Regardless of actual performance, all submissions contribute to the common effort to develop dimensional approaches for affective computing, and the individual report in the proceedings provide useful insights into Chinese sentiment analysis. We hope the data sets collected and annotated for this shared task can facilitate and expedite future development in this research area. Therefore, all data sets with gold standard and scoring script are publicly available 5 .


s2fieldsofstudy:
Computer Science
Mathematics

text:
Space-Bounded OTMs and REG$^{\infty}$

An important theorem in classical complexity theory is that LOGLOGSPACE=REG, i.e. that languages decidable with double-logarithmic space bound are regular. We consider a transfinite analogue of this theorem. To this end, we introduce deterministic ordinal automata (DOAs), show that they satisfy many of the basic statements of the theory of deterministic finite automata and regular languages. We then consider languages decidable by an ordinal Turing machine (OTM), introduced by P. Koepke in 2005 and show that if the working space of an OTM is of strictly smaller cardinality than the input length for all sufficiently long inputs, the language so decided is also decidable by a DOA.

Introduction
Ordinal Turing machines (OTMs), introduced by P. Koepke in [Ko] and independently by B. Dawson in [Da], are a well-established and well-studied model of infinitary computability. Roughly, an OTM is a Turing machine with a tape of proper class size, whose cells are indexed with ordinals, and transfinite ordinal working time. One attractive feature of OTMs when compared with Infinite Time Turing Machines (ITTMs), introduced in 2000 by J. Hamkins and A. Lewis ([HaLe]), is that OTMs exhibit a symmetry between time and space. As a consequence, the complexity theory for OTMs resembles the classical theory much more than it does for ITTMs: For an ITTM, each input is of length ω, so that e.g. the ITTM-analogue of the class P of polynomial-time computable functions is just the class of functions computable with a constant time bound. The consideration of complexity theory for OTMs was taken up by B. Löwe in [L] and then continued by B. Löwe, B. Rin and the author in [CLR].
An important result in classical complexity theory is that the class of languages that are decidable by a Turing-machine with double-logarithmic space bound coincides with the class of regular languages (see e.g. [H]). In this paper, we consider an analogue of this theorem for OTMs. To this end, we introduce deterministic ordinal automata (DOAs) as a transfinite analogue of deterministic finite automata (DFAs). There are several transfinite variants of DFAs preceeding ours: Büchi introduced automata ( [Bu]) that work like DFAs and process words of ordinal length by picking a certain element from the set of states that occured cofinally often during the processing at limit times. Similar models are considered in [StSc] and [HKS]. A common feature of all these models is that the transition relation is given by a set. In contrast, we allow class-sized transition relation that satisfy a certain mild coherence condition. It turns out that this condition suffices to carry over much of the theory of DFAs and regular languages (section 2). To the best of our knowledge, this notion has not been considered before. We then proceed in section 3 to define strictly space-bounded OTM-computations as those whose working space is of a strictly smaller cardinality than the input length and show that such OTMs in fact work with a constant space bound and that the languages so recognized can be recognized with DOAs.
In the following, Σ denotes an alphabet (i.e. a finite set), Σ * * denotes Σ <On , i.e. the set of sequences of ordinal length over Σ.

REG ∞
We consider ordinal analogues of regular languages. In particular, we introduce notions parallelizing in the ordinal realm deterministic finite automata, nondeterministic finite automata, induced congruence relation and prove analogues of classical theorems like simulation of determinism by nondeterminism and Myhill-Nerode. Though our generalization of a finite automaton may seem to be far too liberal at first, it preserves enough of the heart of the classical concept to make large parts of the classical theory go through, and much for the same reasons.
We begin by introducing a notion DOA generalizing deterministic finite automata.
Definition 1. A deterministic ordinal automaton (DOA) is a quintuple (Q, q 0 , F, D, Σ) where Q is a set q 0 ∈ Q, F ⊆ Q and D : Q × Σ * * → Q is a class function with the following property: For all w, w 1 , w 2 ∈ Σ * * , if D(q, w) is defined and w = w 1 w 2 , then D(q, w 1 ) is also defined and we have D(D(q 0 , w 1 ), w 2 ) = D(q, w).
A DOA A is complete if and only if D(q, w) is defined for all q ∈ Q and all w ∈ Σ * * .
Note that, by this definition, the transition relation D is an arbitrary class, only restricted by the 'coherence' or 'forgetfulness' condition in the definition; intuitively, by this condition, the automaton, when in a certain state, has no memory how it got there. It turns out that this rather weak condition seems to lie combinatorially at the heart of many results about regular languages. We demonstrate this by carrying over some of the main standard results in the theory of regular languages, along with their proofs. The classical counterparts can be found in any basic textbook on theoretical computer science, such as [Hro].
We now consider analogues of non-deterministic finite automata. Definition 4. An NOA is a quintuple A = (Q, q 0 , F, D, Σ) and D ⊆ Q × Σ * * × Q is a relation such that we have for all q ∈ Q and all w, w 1 , w 2 ∈ Σ * * with w = w 1 w 2 that D[D(q, w 1 ), w 2 ] = D(q, w). Here, for X ⊆ Q and w ∈ Σ * * , D[X, w] denotes q∈X D(q, w).
If A is an NOA, then S(A) = {w ∈ Σ * * : D(q 0 , w) ∩ F = ∅} is the language accepted by A.
We now imitate the classical power-set construction for simulating nondeterminism by determinism in our setting.
Theorem 5. The languages accepted by some NOA are exactly the languages in REG ∞ .
Proof. Clearly, all REG ∞ languages are accepted by some NOA, as every DOA is an NOA.
Hence A ′ is indeed a DOA. We finish by showing that S(A ′ ) = S(A): We turn to an analogue of Myhill-Nerode.
Definition 6. Let L ⊆ Σ * * . The congruence relation on Σ * * induced by L is defined as follows: For w 1 , w 2 ∈ Σ * * , we have w 1 ≡ L w 2 if and only if, for all w ∈ Σ * * , we have w 1 w ∈ L ↔ w 2 w ∈ L.
If the class of ≡ L -equivalence classes is a set (more formally: if there is a set X such that every w ∈ Σ * * is L-equivalent to some element of X), we say that L satisfies the 'ordinal Myhill-Nerode condition' (MH for short).
Proof. Suppose first that L is REG ∞ , and let, by Thus, all the Z A (q) are subclasses of ≡ L -equivalence classes and, as A is complete, every w ∈ Σ * * belongs to one of the Z A (q). Thus every ≡ Lequivalence class is a union of some (at least one) Z A (q), hence there are at most as many ≡ L -equivalence classes as there are elements in Q, i.e. only set-sized many. Now let L ⊆ Σ * * be such that ≡ L has only set-sized many equivalence classes on Σ * * . Pick a representative from each equivalence class and denote by C their collection; for w ∈ Σ * * , denote by [w] L the element of C equivalent to w. We construct a DOA A with S(A) = S as follows: Let Note that, for all w ∈ Σ * * , we either have It is easy to check that A = (Q, q 0 , F, D, Σ) is as desired.
Corollary 8. REG ∞ is closed under complementation, union and intersection.
For complementation, consider a complete DOA A = (Q, q 0 , D, F, Σ) for Closure under intersection follows by de Morgan's rules from closure under complementation and union.
Corollary 9. For w ∈ {0, 1} * * , let w 0 , w 1 denote the subsequences consisting of the 0s and 1s in w, respectively. Furthermore, let |w| 0 and |w| 1 denote the cardinality of the set of places in w taken by 0 or 1. Then the following two languages are not REG ∞ : ( It is easy to see that the language L ′′ := {0 α 1 β : α, β ∈ On} is REG ∞ : The corresponding DOA has two states s 0 and s 1 , both of which are accepting and of which s 0 is the starting state. The transition relation is given by (1) By Corollary 8, if L was REG ∞ , then so was L∩L ′′ = {0 α 1 α : α ∈ On}; but we saw above that this is not the case. ( We also get a rather straightforward analogue of the pumping lemma. As the proof is the same, we prove something slightly stronger, which is closer to one direction of an analogue of Jaffe's theorem: Let w ∈ Σ * * be sufficiently long, more specifically |w| > card(Q). Then there are α, β < |w| such that, for all Proof. By the pigeonhole-principle and the fact that Remark: The proof clearly allows us to demand that v is 'short', i.e. that β − α ≤ card(Q) + . Note that the proof does not show that we can repeat w ↾ [α, β] also γ many times for γ ∈ On: For example, a DOA with to states s 0 , s 1 may satisfy D(s 0 , 1 i ) = s 0 for any i ∈ ω but also D(s 0 , 1 ω ) = s 1 . We do not know whether this stronger version holds, but we conjecture that it does not. We consider ∞-regularity for unary languages, i.e. languages over an alphabet with only one element.
Proof. The appropriate DOA has one state for each initial segment of an element of S and connects them in the obvious manner.
Definition 13. For X ⊆ On and s a symbol, s X abbreviates {s α : α ∈ X}.
Lemma 14. Neither of the following unary languages is REG ∞ : (1) Proof. All three proofs work by contradiction. For i ∈ {1, 2, 3}, let A i be a DOA with S(A i ) = L i ; the start state is always denoted q 0 , the transition by D, the set of accepting states by F etc. In the following, + always denotes ordinal addition.
For the main result of this paper in the next section, we will also need an ordinal version of λ-NFAs: Definition 16. Fix a special symbol λ. From now on, we will assume that Σ never contains λ. If w ∈ Σ * * , a λ-enrichment of w is defined as a sequence in (Σ ∪ {λ}) * * in which the subsequence of elements of Σ is exactly w.
A λ-NOA with alphabet Σ is simply an NOA with the alphabet Σ ∪ {λ}.
Proof. Clearly, if L is REG ∞ , it is also λ-REG ∞ , as every DOA is also a λ-NOA (where all transitions for words containing λ are undefined).
On the other hand, let L = L(A), where A = (Q, q 0 , F, D, Σ) is a λ-NOA. Then we define an NOA A ′ = (Q, q 0 , F, D ′ , Σ) as follows: For w ∈ Σ * * and q ∈ Q, D ′ (q, w) = {D(q, w ′ ) : w ′ is a λ − enrichment of w}. It is easy to see that this defines an NOA and that L(A) = L(A ′ ).

Remark:
We also haven't considered ordinal versions of Mealy or Moore automata, but we encourage the interested reader to do so.

Space-Bounded OTMs
We now work towards our main result. To this end, we define the space complexity of an OTM-program. This concept was introduced by Löwe in [L].
Definition 18. Let f : On → On be a function and P an OTM-program. P belongs to SPACE ∞ (f ) if and only if there is an ordinal β such that, whenever w is a word of length α > β, the computation of P w uses only the first βf (α) many cells of the scratch tape.
A classical theorem in complexity theory is that, if the space usage s of a Turing machine T is such that 2 2 s(n) ≤ c · n for some c ∈ N, then T in fact has a constant bound on its space usage and hence decides a regular language.
(See e.g. [H] for a proof of this.) We work towards an infinitary version of this. In the following, let f : On → On be a (class) function such that card(f (α)) < card(α) for all sufficiently large α, i.e. f 'lowers cardinalities'. We will begin by showing that, if P belongs to SPACE ∞ (f ) for such an f , then P in fact belongs to SPACE ∞ (1), i.e. there is a uniform constant bound on the amount of cells P uses on the scratch tape.
Theorem 19. Let P be an OTM-program, κ a cardinal, and let w be a 0-1word of minimal length such that P w uses κ many scratch tape cells. Then card(|w|) ≤ κ.
Proof. Let |w| = δ. Moreover, let σ denote the order type of the set of scratch tape cells used in the computation of P w (thus card(σ) = κ). Form the elementary hull H of σ + 1 ∪ {w} in H δ ++ (the set of sets heriditarily of cardinality ≤ δ ++ , where α + denotes the cardinal successor of α). Note that H will in particular contain the computation of P w . Form the transitive collapse M of H, and denote byw the image of w under the collapsing map. Then σ + 1 ⊆ M and M |='Pw uses a set of scratch tape cells or order type σ'. Furthermore, we have |M| = ℵ 0 κ = κ, so the length ofw has cardinality at most κ. Since M is transitive, the computation of Pw in M is the same as that in V . Thus Pw uses already a set of scratch tape cells of order type σ and hence of cardinality κ.
Remark: It is easy to see and well-known that a halting OTM-computation on an input of length α can only have a length of cardinality ≤ card(α). Thus, we can in fact replace card(|w|) ≤ κ with card(|w|) = κ in the theorem statement.
Definition 20. Call an OTM-program P 'strictly space-bounded' if and only if there is a function f : On → On such that card(f (α)) < card(α) for all sufficiently large α and P belongs to SPACE ∞ (f ).
Corollary 21. If P is strictly space-bounded, then P belongs to SPACE ∞ (1).
Proof. Assume otherwise. This means that, for each κ ∈ Card, there is a word w such that P w uses at least κ many scratch tape cells. By Theorem 19, |w| ≤ κ. But, by the definition of f , if κ is sufficiently large, then card(f (κ)) < κ, so since P belongs to SPACE ∞ (f ), P w uses less than κ many scratch tape cells, a contradiction.
Our final goal is to show that, for each OTM-program P with a constant use of scratch tape, there is a λ-NOA accepting exactly those words for which P halts. The proof will use an ordinal version of crossing sequences.
Definition 22. Let P be an OTM-program, and let w = (w ι : ι < α) ∈ {0, 1} * * . Consider the computation of P w and let β < α be an ordinal.The interval [β, β + ω) is called the β-block of w. The block-crossing sequence bcs(β) associated with β is the sequence of quintuples (s, t, ρ, i, f ), called P -snippets, where in the ιth tuple (s ι , t ι , i ι ), s ι is the inner state of P when the reading head is in the β-block of w for the ιth time in the course of the computation, and likewise t ι is the content of the scratch tape, ρ is the position of the read/write-head on the scratch tape, i ∈ ω is the relative position of the reading head in the block at this time and f is the content of the first i many bits of the ω-block in which the reading head is currently located.
For the sake of simplicity, we will from now on regard ρ and s as 'absorbed' into t (e.g. via a special mark on the tape) and work with triples (s, i, f ) instead of quintuples as P -snippets.
We will eventually construct the desired NOA whose states will be the possible candidates for the block-crossing sequences. We begin by showing that the possible block-crossing sequences for such a program P as above form a set. (Note that this is not trivial, since the possible inputs are a proper class.) If P has constant scratch tape use bounded by γ, then the second components of the triples (s, i, f ) will belong to the set γ 2; the first component is an element of a finite set and the last component is an element of ω. Thus, there is a set T of triples that can possibly occur in a block crossing sequence. It remains to control the length of such a sequence. This is our next goal.
We start by recalling the following looping criterion for infinitary machines, which can e.g. be found in [?] for the case of ITTMs: Proposition 23. Let P be an OTM-program. Suppose in the computation of P , a configuration c is repeated such that, for all times between the two occurences of c, every other configuration had all components (tape contents) at least as large as the corresponding component in c. Then P never halts.
Proof. (Sketch) After arriving at c for the second time, the same steps will be repeated, so c will occur a third, fourth etc. time. The only way to escape the loop would be at a limit time. However, the condition above ensures that the configuration at any limit time which is preceeded by cofinally many occurences of c will be c as well.
Lemma 24. Let w = (w ι : ι < α) ∈ {0, 1} * * . In the course of a halting computation P w with scratch tape use bounded by γ, the reading head will be positioned on w 0 less than (2 card γ ) + many times.
Proof. First, note that the sequence (c ι : ι < δ) of machine configurations (i.e. the inner states and the scratch tape contents) occuring at times when the reading head is positioned at w 0 is continuous in the sense that (q λ , s λ ) = liminf ι<λ (s ι , t ι ) for limit ordinals λ < δ. This is due to the behaviour of OTMs at limit stages and in particular the fact that the reading head position at limit times is the inferior limit of the sequence of earlier reading head positions, i.e. at a limit of times at which the reading head was on w 0 , the reading head will again be at w 0 . Now assume otherwise and consider the sequence of the first (2 card(γ) ) + many such configurations. Let ι * be the index in the computation of P w at which the reading head is at w 0 for the (2 card(γ) ) + th time.
If every configuration occurs only boundedly often before this time, then for each such configuration, the set of suprema of the indices of their occurences would be majorized by some c ι , and the set of these ι would be a cofinal subset of (2 card(γ) ) + of cardinality 2 card(γ) , contradicting the regularity of the successor cardinal (2 card(γ) ) + .
Thus, there is some α < ι * such that all configurations occuring after time α in the computation occur cofinally often before ι * . Again by the regularity of (2 card(γ) ) + , there is λ < ι * which is simultaneously for each of these configuration a limit of the indices at which these configurations occur and a time at which the reading head is at w 0 . As λ > α, c λ will occur cofinally often below ι * . Also, by the liminf-rule, c λ will in each component be less than or equal to every other configuration occuring cofinally often before ι * . But this implies that the computation is strongly looping after the first two such occurences of c λ , which contradicts the assumption that P w halts.
Corollary 25. Let β < α. In the course of the computation of P w , there will be at most 2 card(γ) many disjoint time intervals at which the reading head is in the βth block.
Proof. Note that, by the rules for moving the reading head, a block other than the 0th block can only be reached "from the left", while the 0th block can only be entered when the reading head is moved to the left from some limit position. Therefore, whenever the reading head is in the 0th block, it must have been on w 0 before without leaving the 0th block in the meantime. Thus, the 0th block can only be visited < 2 card γ ) + , i.e. ≤ 2 card(γ) many times by Lemma 24.
As any other block can only be entered from the left, the reading head must have been in the 0th block before entering such a block anew, thus the same holds for all other blocks.
It remains to control how long the reading head can remain in a block.
Lemma 26. A time interval in which the reading head remains in the same ω-block can have no more than 2 card(γ) many elements.
Proof. Suppose for a contradiction that the reading head remains in some block for (2 card(γ) ) + many steps. Shifting the time interval if necessary, we assume that this starts at computation time 0. If every of the possible ω many reading head positions in this episode occured only boundedly often, (2 card(γ) ) + would have cofinality ω, a contradiction. Thus, there is α < (2 card(γ) ) + such that every reading head position occuring after time α occurs cofinally often before time (2 card(γ) ) + . Let k be the minimal element of the set of these positions. Then the same argument as for Lemma 24 shows that the reading head can be on position k at most 2 card(γ) many times during the interval. But this leads to a cofinal subset of (2 card(γ) ) + with cardinality ≤ 2 card(γ) , a contradiction.
Corollary 27. For each block, the reading head position is inside this block at most 2 card(γ) many times during the computation of P w .
Proof. By Corollary 25, the reading head enters each block at most 2 card(γ) many times and by Lemma 26 remains there for at most 2 card(γ) many steps, thus the reading head is inside the block at most 2 card(γ) 2 card(γ) = 2 card(γ) many times.
Corollary 28. There are at most 2 2 card(γ) many possible block crossing sequences.
We will now construct an NOA that accepts exactly those words w ∈ {0, 1} * * for which P w halts. As announced above, the states of this NOA will be the possible block crossing sequences.
We assume that the input word w has a mark lh on its left side and another mark rh to its right and that P notices (via special states) when rh reached. Furthermore, we assume that P starts with the reading head on lh and never goes back there in the course of the computation.
We change the definition of a block-crossing sequence slightly: We don't need the whole sequence of machine configurations while the reading head is on the block, it suffices to have the sequence of machine configurations for the time points when the reading head enters the block anew (i.e. after having been in another block in the meantime). (Clearly, as such sequences are obtained from the others by deleting some elements, they are not longer and hence the estimates above remain valid.) Theorem 29. Let P be an OTM-program such that the scratch space usage of the computation of P w for every w ∈ {0, 1} * * is bounded by a constant γ. Then there is a λ-NOA A P such that S(A P ) = {w ∈ {0, 1} * * : P w ↓} =: S(P ).
Proof. Assume without loss of generality that, if P w halts, then it halts with the reading head on rh. This can easily be arranged by changing P slightly to P ′ which works like P , but when P assumes a halting state, moves the reading head to the right until it reaches rh and stops then.
We pick a starting state q 0 . Now let S P be the set of all P -snippets in which the scratch tape is empty, the inner state of P is the initial state and the reading and read/write heads are on position 0. Furthermore, let Seq P be the set of all sequences of P -snippets of length ≤ 2 card(γ) whose first elements belongs to S P . The λ-NOA we are about to build will have disjoint deterministic components A z , one for each z ∈ Seq P . The idea is that z is a guess for the sequence of snippets when P has the reading head at the start of the input tape. Thus the first step of A is a λ-transition to some element of Seq P . Hence, for each z ∈ Seq P , we introduce a state q z to the states of A and add λ-transitions D(q 0 , λ) = {q z : z ∈ Seq P } to the class of transitions of A.
We now define the components A z separately. Let z ∈ Seq P be given. The states of A z are all sequences of P -snippets of length ≤ 2 card(γ) . We proceed to define the transition relation D z of A z .
First, let q = (s, i, f ) be a P -snippet, w ∈ {0, 1} * * . Then d z (q, w), the local w-successor of q, is determined as follows: Add w to the right of f . Then simulate P from this situation on, with the input given by f w. If the reading head is set back to 0 before every bit of w has been read, we let d z (q, w) = ∅. Otherwise, we consider the P -snippet c describing the situation in which the reading head arrives at a cell to the right of w for the first time and let d z (q, w) = c.
Next, we define D z (s, w), for s ∈ Seq P . Let s = (s ι : ι ≤ 2 card(γ) ). Then D z (s, w) = (d z (s ι , w) : ι ≤ 2 card(γ) ), if it holds for all s ι with d z (s ι , w) = ∅ that the (ι + 1)th entry of z is the P -snippet after the reading head is set back to 0; otherwise, we leave D z (s, w) undefined. This condition enforces that the P -snippets 'match' the initial situation z.
The set F z of accepting states of A z is the set of sequences that have a final entry t in which the inner state is an accepting state of P . This defines A z , and thus A.
Let A P = (Q, q 0 , F, D, {0, 1}). We show that A P is indeed a λ-NOA. But this is easy to see, as the indeterminism in fact only happens in the first step of the form D(q 0 , λ), while for q = q 0 , D(q, w) has only one element.
Finally, we show that S(A P ) = S(P ). First, if P w halts, then D(q 0 , w) contains the sequences describing the actual behaviour of P w on w (ω) , the sequence of the first ω many bits of w. Now, ifw denotes the rest of w, then D(s,w) will be the crossing sequence describing the actual behaviour of P w on rh, which, by the assumption that P w halts, has as its last element a triple whose first component is a halting state and all of whose other entries must have an rh-state as their first component.
On the other hand, if w ∈ S(A P ), this means that D(q 0 , w) contains an element of F , which by definition of D means that there is a computation of P w that halts.
Putting Corollary 30 and our negative results on REG ∞ together, we obtain: Corollary 31. None of the following languages is semi-decidable by a strictly space-bounded OTM: