广义量词的计算复杂性

摘要

There are two levels of complexity of generalized quantifiers syntactic level and semantic level. The paper focuses on complexity of semantic of generalized quantifiers. The complexity of the truth-val⁃ues of natural language quantified sentences can be found in finite situations. The complexity is related to oth⁃er contents, such as computability in Turing machines, identify of meanings-as algorithms, computational com⁃plexity, tractability and intractability. There are many related fruits in computational complexity of generalized quantifiers.%广义量词的复杂性有两个层次：句法层面的复杂性和语义层面的复杂性，我们集中研究了广义量词的语义复杂性。在有穷的语境中可以找出自然语言量化语句真值的复杂性。这些复杂性与图灵机中的可计算性、作为算法的意义的等价性、计算复杂性、易处理性和不易处理性等内容相关。广义量词计算复杂性已有诸多相关研究成果。