有限理性博弈问题和自适应博弈学习模型

有限理性参与者之间的博弈问题是人们十分关注的研究项目.目前已提出了一些博弈学习模型,但都存在一定的局限性,本文给出了博弈学习的一个改进方法,建立了新的博弈学习模型.计算机实验表明,新的博弈学习方法的实用性和有效性有了很大的提高.     

基于有限理性Agent的人工股票市场模型

从现实交易者的有限理性角度,描述了基于Agent的股票市场模型,研究设计了带有认知偏误的交易者Agent,分析了多Agent之间的相互关系,指出了心理因素在其中的重要作用。通过对连续双向拍卖交易收敛到竞争均衡过程的分析,发现了与有效市场假设相悖的结果。     

BRA: An Algorithm for Simulating Bounded Rational Agents

This paper describes a simulation approach for modelling decision-making processes under incomplete and imperfect information in Agent-based Computational Economics (ACE). The main idea is to represent decision-making in a model-free framework that can be applied to a larger set of simulation problems, not just the domain modelled. The method translates some basic sociopsychological concepts from the bounded rationality and learning literature into an executable algorithm. In a simple example, the algorithm is applied in the domain of behavioural game theory, illustrating how the algorithm can be used to reproduce observed patterns of human behaviour.     

Rational Task Analysis: A Methodology to Benchmark Bounded Rationality

How can we study bounded rationality? We answer this question by proposing rational task analysis (RTA)—a systematic approach that prevents experimental researchers from drawing premature conclusions regarding the (ir-)rationality of agents. RTA is a methodology and perspective that is anchored in the notion of bounded rationality and aids in the unbiased interpretation of results and the design of more conclusive experimental paradigms. RTA focuses on concrete tasks as the primary interface between agents and environments and requires explicating essential task elements, specifying rational norms, and bracketing the range of possible performance, before contrasting various benchmarks with actual performance. After describing RTA’s core components we illustrate its use in three case studies that examine human memory updating, multitasking behavior, and melioration. We discuss RTA’s characteristic elements and limitations by comparing it to related approaches. We conclude that RTA provides a useful tool to render the study of bounded rationality more transparent and less prone to theoretical confusion.     

Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables

Abstract. We consider generalized first-order sentences over < using both ordinary and modular quantifiers. It is known that the languages definable by such sentences are exactly the regular languages whose syntactic monoids contain only solvable groups. We show that any sentence in this logic is equivalent to one using three variables only, and we prove that the languages expressible with two variables are those whose syntactic monoids belong to a particular pseudovariety of finite monoids, namely the wreath product of the pseudovariety DA (which corresponds to the languages definable by ordinary first-order two-variable sentences) with the pseudovariety of finite solvable groups. This generalizes earlier work of Thérien and Wilke on the expressive power of two-variable formulas in which only ordinary quantifiers are present. If all modular quantifiers in the sentence are of the same prime modulus, this provides an algorithm to decide if a regular language has such a two-variable definition.     

Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables

Abstract. We consider generalized first-order sentences over < using both ordinary and modular quantifiers. It is known that the languages definable by such sentences are exactly the regular languages whose syntactic monoids contain only solvable groups. We show that any sentence in this logic is equivalent to one using three variables only, and we prove that the languages expressible with two variables are those whose syntactic monoids belong to a particular pseudovariety of finite monoids, namely the wreath product of the pseudovariety DA (which corresponds to the languages definable by ordinary first-order two-variable sentences) with the pseudovariety of finite solvable groups. This generalizes earlier work of Thérien and Wilke on the expressive power of two-variable formulas in which only ordinary quantifiers are present. If all modular quantifiers in the sentence are of the same prime modulus, this provides an algorithm to decide if a regular language has such a two-variable definition.     

Logic and Rational Languages of Words Indexed by Linear Orderings

We prove that every rational language of words indexed by linear orderings is definable in monadic second-order logic. We also show that the converse is true for the class of languages indexed by countable scattered linear orderings, but false in the general case. As a corollary we prove that the inclusion problem for rational languages of words indexed by countable linear orderings is decidable.     

试论基于Ada的PDL

本文首先讨论了PDL的历史、定义、特性与要求以及与高级语言的联系与区别,分析了研制基于Ada的PDL的必要性、应用范围、与Ada语言及软件设计方法论的关系,探讨了支撑基于Ada的PDL的工具与环境,接着简述了几个典型的基于Ada的PDL。最后讨论了一些悬而未决的问题。     

On Bounded Leg Shortest Paths Problems

Let V be a set of points in a d-dimensional l _p -metric space. Let s,t∈V and let L be a real number. An L-bounded leg path from s to t is an ordered set of points which connects s to t such that the leg between any two consecutive points in the set has length of at most L. The minimal path among all these paths is the L-bounded leg shortest path from s to t. In the s–t Bounded Leg Shortest Path (stBLSP) problem we are given two points s and t and a real number L, and are required to compute an L-bounded leg shortest path from s to t. In the All-Pairs Bounded Leg Shortest Path (apBLSP) problem we are required to build a data structure that, given any two query points from V and a real number L, outputs the length of the L-bounded leg shortest path (a distance query) or the path itself (a path query). In this paper we obtain the following results:     

Unique Decipherability in the Monoid of Languages: An Application of Rational Relations

We attack the problem of deciding whether a finite collection of finite languages is a code, that is, possesses the unique decipherability property in the monoid of finite languages. We investigate a few subcases where the theory of rational relations can be employed to solve the problem. The case of unary languages is one of them and as a consequence, we show how to decide for two given finite subsets of nonnegative integers, whether they are the nth root of a common set, for some n≥1. We also show that it is decidable whether a finite collection of finite languages is a Parikh code, in the sense that whenever two products of these sets are commutatively equivalent, so are the sequences defining these products. Finally, we consider a nonunary special case where all finite sets consist of words containing exactly one occurrence of the specific letter.     

On Database Systems viewed as Programming Languages

At present an extremely complex system of specific ideas and notions has been developed in the domain of Database Systems. These ideas and notions are perplexing designers as well as users thus turning out a hindrance rather then a tool for development and implementation of Information Systems dealing with Data. The present paper aims to show that these ideas and notions are dispensable altogether since Data Information Systems (Database Systems) may be conceived and developed strictly within the scope of ideas of Programming Languages and in standard terms of this field. In this paper the notions of Information System, Data- and Semantic Information are analyzed and compared. Information Systems dealing with Data (Database Systems) are interpreted as Programming Languages. The approach is discussed and illustrated by one of the pilot versions currently being implemented at the Technische Universität Berlin.     

On the Regularity of Petri Net Languages

Petri nets are known to be useful for modeling concurrent systems. Once modeled by a Petri net, the behavior of a concurrent system can be characterized by the set of all executable transition sequences, which in turn can be viewed as a language over an alphabet of symbols corresponding to the transitions of the underlying Petri net. In this paper, we study the language issue of Petri nets from a computational complexity viewpoint. We analyze the complexity of theregularity problem(i.e., the problem of determining whether a given Petri net defines an irregular language or not) for a variety of classes of Petri nets, includingconflict-free,trap-circuit,normal,sinkless,extended trap-circuit,BPP, andgeneralPetri nets. (Extended trap-circuit Petri nets are trap-circuit Petri nets augmented with a specific type ofcircuits.) As it turns out, the complexities for these Petri net classes range from NL (nondeterministic logspace), PTIME (polynomial time), and NP (nondeterministic polynomial time), to EXPSPACE (exponential space). In the process of deriving the complexity results, we develop adecomposition approachwhich, we feel, is interesting in its own right, and might have other applications to the analysis of Petri nets as well. As a by-product, an NP upper bound of the reachability problem for the class of extended trap-circuit Petri nets (which properly contains that of trap-circuit (and hence, conflict-free) and BPP-nets, and is incomparable with that of normal and sinkless Petri nets) is derived.     

On the Geometric Modelling of Visual Languages

We present arguments for the complementary role that intrinsically geometric models of visual languages can play in many applications, alongside non-geometry based models (such those based on graph grammars, logical predicates or algebraic structures). We characterise which models are intrinsically geometric, and illustrate the concept by providing such a model for higraphs. Further, we examine the relevance of geometric models to the design and implementation of tools which effectively support users in working with visual languages.     

On the Expressiveness of Linda-like Concurrent Languages

We compare the expressiveness of a class of concurrent languages that employ asynchronous communication primitives à la Linda. All the languages considered contain sequential, parallel and choice operators, and they differ from one another in the set of communication primitives used. These primitives include tell, get and ask operations for adding, deleting, and checking for the presence of data in a dataspace shared by a number of concurrent processes, as well as a nask (negative ask) operation for checking for the absence of data in the shared dataspace. We use the notion of modular embedding introduced by De Boer and Palamidessi in [3] to compare the relative expressive power of the languages. A first result is the formalisation of the intuitive separation result stating that the language with get and tell is strictly more expressive than the language with ask and tell operations. An interesting result is that the ability to check for the presence of information (ask) does not increase the power of a language containing get and tell operations, whereas the ability to check for the absence of information (nask) does increase the power of such a language. Another interesting result shown is that the language containing all the communication primitives considered is strictly more expressive than each of its sub-languages, except for the redundancy of ask.