Invariant-free deduction systems for temporal logic

In this thesis we propose a new approach to deduction methods for temporal logic. Our proposal is based on an inductive definition of eventualities that is different from the usual one. On the basis of this non-customary inductive definition for eventualities, we first provide dual systems of tableaux and sequents for Propositional Linear-time Temporal Logic (PLTL). Then, we adapt the deductive approach introduced by means of these dual tableau and sequent systems to the resolution framework and we present a clausal temporal resolution method for PLTL. Finally, we make use of this new clausal temporal resolution method for establishing logical foundations for declarative temporal logic programming languages. The key element in the deduction systems for temporal logic is to deal with eventualities and hidden invariants that may prevent the fulfillment of eventualities. Different ways of addressing this issue can be found in the works on deduction systems for temporal logic. Traditional tableau systems for temporal logic generate an auxiliary graph in a first pass.Then, in a second pass, unsatisfiable nodes are pruned. In particular, the second pass must check whether the eventualities are fulfilled. The one-pass tableau calculus introduced by S. Schwendimann requires an additional handling of information in order to detect cyclic branches that contain unfulfilled eventualities. Regarding traditional sequent calculi for temporal logic, the issue of eventualities and hidden invariants is tackled by making use of a kind of inference rules (mainly, invariant-based rules or infinitary rules) that complicates their automation. A remarkable consequence of using either a two-pass approach based on auxiliary graphs or aone-pass approach that requires an additional handling of information in the tableau framework, and either invariant-based rules or infinitary rules in the sequent framework, is that temporal logic fails to carry out the classical correspondence between tableaux and sequents. In this thesis, we first provide a one-pass tableau method TTM that instead of a graph obtains a cyclic tree to decide whether a set of PLTL-formulas is satisfiable. In TTM tableaux are classical-like. For unsatisfiable sets of formulas, TTM produces tableaux whose leaves contain a formula and its negation. In the case of satisfiable sets of formulas, TTM builds tableaux where each fully expanded open branch characterizes a collection of models for the set of formulas in the root. The tableau method TTM is complete and yields a decision procedure for PLTL. This tableau method is directly associated to a one-sided sequent calculus called TTC. Since TTM is free from all the structural rules that hinder the mechanization of deduction, e.g. weakening and contraction, then the resulting sequent calculus TTC is also free from this kind of structural rules. In particular, TTC is free of any kind of cut, including invariant-based cut. From the deduction system TTC, we obtain a two-sided sequent calculus GTC that preserves all these good freeness properties and is finitary, sound and complete for PLTL. Therefore, we show that the classical correspondence between tableaux and sequent calculi can be extended to temporal logic. The most fruitful approach in the literature on resolution methods for temporal logic, which was started with the seminal paper of M. Fisher, deals with PLTL and requires to generate invariants for performing resolution on eventualities. In this thesis, we present a new approach to resolution for PLTL. The main novelty of our approach is that we do not generate invariants for performing resolution on eventualities. Our method is based on the dual methods of tableaux and sequents for PLTL mentioned above. Our resolution method involves translation into a clausal normal form that is a direct extension of classical CNF. We first show that any PLTL-formula can be transformed into this clausal normal form. Then, we present our temporal resolution method, called TRS-resolution, that extends classical propositional resolution. Finally, we prove that TRS-resolution is sound and complete. In fact, it finishes for any input formula deciding its satisfiability, hence it gives rise to a new decision procedure for PLTL. In the field of temporal logic programming, the declarative proposals that provide a completeness result do not allow eventualities, whereas the proposals that follow the imperative future approach either restrict the use of eventualities or deal with them by calculating an upper bound based on the small model property for PLTL. In the latter, when the length of a derivation reaches the upper bound, the derivation is given up and backtracking is used to try another possible derivation. In this thesis we present a declarative propositional temporal logic programming language, called TeDiLog, that is a combination of the temporal and disjunctive paradigms in Logic Programming. We establish the logical foundations of our proposal by formally defining operational and logical semantics for TeDiLog and by proving their equivalence. Since TeDiLog is, syntactically, a sublanguage of PLTL, the logical semantics of TeDiLog is supported by PLTL logical consequence. The operational semantics of TeDiLog is based on TRS-resolution. TeDiLog allows both eventualities and always-formulas to occur in clause heads and also in clause bodies. To the best of our knowledge, TeDiLog is the first declarative temporal logic programming language that achieves this high degree of expressiveness. Since the tableau method presented in this thesis is able to detect that the fulfillment of an eventuality is prevented by a hidden invariant without checking for it by means of an extra process, since our finitary sequent calculi do not include invariant-based rules and since our resolution method dispenses with invariant generation, we say that our deduction methods are invariant-free.

MPI parallel programming of mixed integer optimization problems using CPLEX with COIN-OR

The aim of this technical report is to present some detailed explanations in order to help to understand and use the Message Passing Interface (MPI) parallel programming for solving several mixed integer optimization problems. We have developed a C++ experimental code that uses the IBM ILOG CPLEX optimizer within the COmputational INfrastructure for Operations Research (COIN-OR) and MPI parallel computing for solving the optimization models under UNIX-like systems. The computational experience illustrates how can we solve 44 optimization problems which are asymmetric with respect to the number of integer and continuous variables and the number of constraints. We also report a comparative with the speedup and efficiency of several strategies implemented for some available number of threads.

Media translation and lesser-used languages: implications of subtitles for Irish language broadcastind

Eguíluz, Federico; Merino, Raquel; Olsen, Vickie; Pajares, Eterio; Santamaría, José Miguel (eds.)

Processing Facilitation Strategies in OV and VO Languages: A Corpus Study

The present corpus study aimed to examine whether Basque (OV) resorts more often than Spanish (VO) to certain grammatical operations, in order to minimi ze the number of arguments to be processed before the verb. Ueno & Polinsky (2009) argue that VO/OV languages use certain grammatical resources with different frequencies in order to facilitate real-time processing. They observe that both OV and VO languages in their sample (Japanese, Turkish and Spanish) have a similar frequency of use of subject pro-drop; however, they find that OV languages (Japanese, Turkish) use more intransitive sentences than VO languages (English, Spanish), and conclude this is an OV-specific strategy to facilitate processing. We conducted a comparative corpus study of Spanish (VO) and Basque (OV). Results show (a) that the fre- quency of use of subject pro-drop is higher in Basque than in Spanish; and (b) Basque does not use more intransitive sentences than Spanish; both languages have a similar frequency of intransitive sentences. Based on these findings, we conclude that the frequency of use of grammatical resources to facilitate the processing does not depend on a single typological trait (VO/OV) but it is modulated by the concurrence of other grammatical feature.

THE AINU LANGUAGES: TRADITIONAL RECONSTRUCTION, EURASIAN AREAL LINGUISTICS, AND DIACHRONIC (HOLISTIC) TYPOLOGY

El objetivo principal de esta tesis doctoral es, en primer lugar, ofrecer una reconstrucción alternativa del protoainu para, en segundo lugar, aplicar conceptos de tipología diacrónicaholística con el fin de discernir algún patrón evolutivo que ayude a responder a la pregunta:¿por qué la lengua ainu es como es en su contexto geolingüístico (lengua AOV con prefijos),cuando en la región euroasiática lo normal es encontrar el perfil 'lengua AOV con sufijos'? En suma, se trata de explorar las posibilidades que ofrece la tipología diacrónica holística,combinada con métodos más tradicionales, en la investigación de las etapas prehistóricas delenguas aisladas, es decir, sin parientes conocidos, como el ainu, el vasco, el zuñi o elburushaski. Este trabajo se divide en tres grandes bloques con un total de ocho capítulos, unapéndice con las nuevas reconstrucciones protoainúes y la bibliografía.El primer bloque se abre con el capítulo 1, donde se hace una breve presentación delas lenguas ainus y su filología. El capítulo 2 está dedicado a la reconstrucción de la fonologíaprotoainu. La reconstrucción pionera pertenece a A. Vovin (1992), que de hecho sirve comobase sobre la que ampliar, corregir o modificar nuevos elementos. En el capítulo 3 se describela morfología histórica de las lenguas ainus. En el capítulo 4 se investiga esta opción dentrode un marco más amplio que tiene como objetivo analizar los patrones elementales deformación de palabras. El capítulo 5, con el que se inicia el segundo bloque, da cabida a lapresentación de una hipótesis tipológica diacrónica, a cargo de P. Donegan y D. Stampe, conla que especialistas en lenguas munda y mon-khmer han sido capaces de alcanzar unreconstrucción del protoaustroasiático según la cual el tipo aglutinante de las lenguas mundasería secundario, frente al original monosilábico de las lenguas mon-khmer. En el capítulo 6se retoma la perspectiva tradicional de la lingüística geográfica, pero no se olvidan algunas delas consideraciones tipológicas apuntadas en el capítulo anterior (el hecho de que la hipótesisde Donegan y Stampe no funcione con el ainu no significa que la tipología diacrónica nopueda ser todavía de utilidad). En el capítulo 7 se presentan algunas incongruencias queresultan tras combinar las supuestas evidencias arqueológicas con el escenario lingüísticodescrito en capítulos anteriores. Las conclusiones generales se presentan en el capítulo 8. Elapéndice es una tabla comparativa con las dos reconstrucciones disponibles a fecha de hoypara la lengua protoainu, es decir, las propuestas por A. Vovin en su estudio seminal de 1992y en el capítulo 3 de la presente tesis. Dicha tabla incluye 686 reconstrucciones (puedehacerse una sencilla referencia cruzada con Vovin, puesto que ambas están ordenadasalfabéticamente).

Proficiency, Attitude and Conventions in Minority Languages

In this paper we study a simple mathematical model of a bilingual community in which all agents are f luent in the majority language but only a fraction of the population has some degree of pro ficiency in the minority language. We investigate how different distributions of pro ficiency, combined with the speaker´attitudes towards or against the minority language, may infl uence its use in pair conversations.

Discriminating languages in bilingual contexts: the impact of orthographic markedness

Does language-specific orthography help language detection and lexical access in naturalistic bilingual contexts? This study investigates how L2 orthotactic properties influence bilingual language detection in bilingual societies and the extent to which it modulates lexical access and single word processing. Language specificity of naturalistically learnt L2 words was manipulated by including bigram combinations that could be either L2 language-specific or common in the two languages known by bilinguals. A group of balanced bilinguals and a group of highly proficient but unbalanced bilinguals who grew up in a bilingual society were tested, together with a group of monolinguals (for control purposes). All the participants completed a speeded language detection task and a progressive demasking task. Results showed that the use of the information of orthotactic rules across languages depends on the task demands at hand, and on participants' proficiency in the second language. The influence of language orthotactic rules during language detection, lexical access and word identification are discussed according to the most prominent models of bilingual word recognition.

Distribution of Healthcare resources II.Study and Comparison of a Linear Programming Problem and its Dual. Resolution and Evaluation of a Practical Case and its Programming using Excel and Win QSB.

[EN]This research had as primary objective to model different types of problems using linear programming and apply different methods so as to find an adequate solution to them. To achieve this objective, a linear programming problem and its dual were studied and compared. For that, linear programming techniques were provided and an introduction of the duality theory was given, analyzing the dual problem and the duality theorems. Then, a general economic interpretation was given and different optimal dual variables like shadow prices were studied through the next practical case: An aesthetic surgery hospital wanted to organize its monthly waiting list of four types of surgeries to maximize its daily income. To solve this practical case, we modelled the linear programming problem following the relationships between the primal problem and its dual. Additionally, we solved the dual problem graphically, and then we found the optimal solution of the practical case posed through its dual, following the different theorems of the duality theory. Moreover, how Complementary Slackness can help to solve linear programming problems was studied. To facilitate the solution Solver application of Excel and Win QSB programme were used.

Hizkuntza komunikaziorako gaitasuna lantzeko ikuspegi berriak: teoriatik praktikara

[EUS] Gure gaur egungo gizarte globalizatuak, internazionalki komunikatzeko beharra areagotu du, eta horregatik atzerriko hizkuntzak ikastea ezinbestekoa bihurtu da. Eskola errealitatearen isla denez, behar horri aurre egiteko, gero eta gehiago dira irakaskuntza eleaniztuna garatzeko ikuspegi metodologikoak. Ikuspegi metodologiko hauen artean, CLIL/HEBI eta HTB dira garrantzitsuenetarikoak. HEBIk hizkuntzak eta edukiak batera ikasteari egiten dio erreferentzia, eta HTBk curriculumeko hizkuntzen programazio adostuari. Lan honetan metodologia hauen nondik norakoak aztertzen dira, baita hauek ikastetxe batean nolako ibilbidea izan duten eta nola lantzen diren ere. Azken honetan ikastetxearen eta ikasleen aldetik HEBIrekiko dagoen jarrera aztertzen da, galdetegi batzuen bitartez.