Results for 'duplicator'

8 found
Order:
  1. Across-the-Board Binding Meets Verb Second.Anna Szabolcsi - 1990 - In M. Nespor & J. Mascaro (eds.), Grammar in progress. Foris.
    Right-node raising of anaphors and bound pronouns out of coordinations, as in "Every student likes, and every professor hates, himself / his neighbors" is judged more acceptable in German and Dutch than in English. Using combinatory categorial grammar, this paper ties the cross-linguistic difference to the fact that German and Dutch are V-2 languages, and V-2 necessitates a lifted category for verbs that automatically caters to the right-node raised duplicator. The same lifted category is optionally available in English, but (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  2. Binding On the Fly: Cross-Sentential Anaphora in Variable— Free Semantics.Anna Szabolcsi - 2003 - In R. Oehrle & J. Kruijff (eds.), Resource Sensitivity, Binding, and Anaphora. Kluwer Academic Publishers. pp. 215--227.
    Combinatory logic (Curry and Feys 1958) is a “variable-free” alternative to the lambda calculus. The two have the same expressive power but build their expressions differently. “Variable-free” semantics is, more precisely, “free of variable binding”: it has no operation like abstraction that turns a free variable into a bound one; it uses combinators—operations on functions—instead. For the general linguistic motivation of this approach, see the works of Steedman, Szabolcsi, and Jacobson, among others. The standard view in linguistics is that reflexive (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  6
    On Winning Ehrenfeucht Games and Monadic NP.Thomas Schwentick - 1996 - Annals of Pure and Applied Logic 79 (1):61-92.
    Inexpressibility results in Finite Model Theory are often proved by showing that Duplicator, one of the two players of an Ehrenfeucht game, has a winning strategy on certain structures.In this article a new method is introduced that allows, under certain conditions, the extension of a winning strategy of Duplicator on some small parts of two finite structures to a global winning strategy.As applications of this technique it is shown that • — Graph Connectivity is not expressible in existential (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  44
    An Ehrenfeucht‐Fraïssé Class Game.Wafik Boulos Lotfallah - 2004 - Mathematical Logic Quarterly 50 (2):179-188.
    This paper introduces a new Ehrenfeucht-Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai-Fagin game to the case when there are several alternating moves played in different models. The game allows Duplicator to delay her choices of the models till the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  5.  32
    Comparing the Power of Games on Graphs.Ronald Fagin - 1997 - Mathematical Logic Quarterly 43 (4):431-455.
    The descriptive complexity of a problem is the complexity of describing the problem in some logical formalism. One of the few techniques for proving separation results in descriptive complexity is to make use of games on graphs played between two players, called the spoiler and the duplicator. There are two types of these games, which differ in the order in which the spoiler and duplicator make various moves. In one of these games, the rules seem to be tilted (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  6.  17
    NP-Completeness of a Combinator Optimization Problem.M. S. Joy & V. J. Rayward-Smith - 1995 - Notre Dame Journal of Formal Logic 36 (2):319-335.
    We consider a deterministic rewrite system for combinatory logic over combinators , and . Terms will be represented by graphs so that reduction of a duplicator will cause the duplicated expression to be "shared" rather than copied. To each normalizing term we assign a weighting which is the number of reduction steps necessary to reduce the expression to normal form. A lambda-expression may be represented by several distinct expressions in combinatory logic, and two combinatory logic expressions are considered equivalent (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  7.  5
    On Complexity of Ehrenfeucht–Fraïssé Games.Bakhadyr Khoussainov & Jiamou Liu - 2009 - Annals of Pure and Applied Logic 161 (3):404-415.
    In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game ? (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  8.  9
    An Ehrenfeucht-Fraisse Class Game.Wafik Lotfallah - 2004 - Mathematical Logic Quarterly 50 (2):179-188.
    This paper introduces a new Ehrenfeucht-Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai-Fagin game to the case when there are several alternating moves played in different models. The game allows Duplicator to delay her choices of the models till the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark