Numeration Systems on a Regular Language

Generalizations of positional number systems in which N is recognizable by finite automata are obtained by describing an arbitrary infinite regular language according to the lexicographic ordering. For these systems of numeration, we show that ultimately periodic sets are recognizable. We also study translation and multiplication by constants as well as the order-dependence of the recognizability. Received March 12, 1999. Online publication December 4, 2000.     

一种新的正则语言的判定方法

针对当前的一些正则语言的判断方法,本文指出了其中的不足之处,在右同余等概念的基础上,通过在语言的符号集中引入等价关系,提出了判断某一给定语言是否是正则语言的代数判定定理,并与原有方法进行了对比。     

One-Nonterminal Conjunctive Grammars over a Unary Alphabet

Systems of equations of the form X _i =φ _i (X ₁,…,X _n ) (1≤ i ≤ n) are considered, in which the unknowns are sets of natural numbers. Expressions φ _i may contain the operations of union, intersection and elementwise addition \(S+T=\{m+n\mid m\in S\), n∈T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars.     

Special Feature Program Measurements on a High-Level Language Computer

Analysis of programs on the Symbol computer helped evaluate its unique architecture and provided insight into the use of programming languages in general.     

一种Java平台上契约式语言的设计与实现

针对游戏机器人开发平台在图形编程过程中可能出现的错误,提出了一种基于契约式设计思想的程序设计语言扩展方式.它为Java语言提供了契约式设计的支持,能帮助本平台的用户发现程序中存在的逻辑上或者设计上的错误,提供改正错误的手段.     

A Tight Lower Bound for a Special Case of Quadratic 0–1 Programming

We consider a still NP-complete partial case of the unconstrained binary quadratic optimization problem that can be described in terms of an undirected graph with red edges having negative weights and green edges having positive weights. The maximum vertex degree of the graph is three. It can be assumed w.l.o.g. that every vertex is incident to a red and a green edge. We are looking for a vertex cover with respect to the red edges which covers a subset of green edges of total weight as small as possible. We prove that for all connected such graphs except a subclass of special graphs having exactly five green edges it is possible to find a vertex cover with respect to the red edges for which the total weight of uncovered green edges is at least 1/4 fraction of the total weight of all green edges.     

Regular Language Representations in the Constructive Type Theory of Coq

We explore the theory of regular language representations in the constructive type theory of Coq. We cover various forms of automata (deterministic, nondeterministic, one-way, two-way), regular expressions, and the logic WS1S. We give translations between all representations, show decidability results, and provide operations for various closure properties. Our results include a constructive decidability proof for the logic WS1S, a constructive refinement of the Myhill-Nerode characterization of regularity, and translations from two-way automata to one-way automata with verified upper bounds for the increase in size. All results are verified with an accompanying Coq development of about 3000 lines.     

The Role of a Natural Language Conversational Interface in Online Sales: A Case Study

This paper describes the evaluation of a natural language dialog-based navigation system (HappyAssistant) that helps users access e-commerce sites to find relevant information about products and services. The prototype system leverages technologies in natural language processing and human-computer interaction to create a faster and more intuitive way of interacting with websites, especially for less experienced users. The result of a comparative study shows that users prefer the natural language-enabled navigation two to one over the menu driven navigation. In addition, the study confirmed the efficiency of using natural language dialog in terms of the number of clicks and the amount of time required to obtain the relevant information. In the case study, as compared to the menu driven system, the average number of clicks used in the natural language system was reduced by 63.2% and the average time was reduced by 33.3%.     

一元函数表达式的类设计

在一些数学软件、统计软件和数值模拟软件中需要的一元函数表达式并不确定。因此,需要一种方法能够动态生成任意复杂的一元函数表达式。本文提出了一种构造函数表达式的动态组合法,该方法将四则运算符、基本初等函数、复合函数和常数项看成是对象,并采用C＋＋实现了这些对象的类定义。通过这些对象的动态创建与组合可以复合成任意的一元函数表达式。结果表明,一元函数表达式对象能够通过接口向其调用者输出正确的表达式计算功能。     

Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines

We design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines, with the same processing time on either machine. (This is a special case of so-called restricted assignment, where the set of eligible machines can be arbitrary for each job.) This is the first improvement of the approximation ratio 2 of Lenstra, Shmoys, and Tardos (Math. Program. 46:259–271, 1990), to a smaller constant for any special case with unbounded number of machines and unbounded processing times. We conclude by showing integrality gaps of several relaxations of related problems.     

Complexity of Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints Between Regular Open Terms

In this paper we study the satisfiability problem for language equations and constraints between regular open terms. We prove that: the constraint problem is PSPACE-complete, the regular language matching problem is EXPSPACE-complete even if we ask about satisfiability by regular languages, satisfiability of word-like language equations is in PSPACE, the finite solution problem is EXPSPACE-complete.     

Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth

It has recently been proved (Je?, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.     

Nash Equilibrium in a Special Case of Symmetric Resource Extraction Games

Cybernetics and Systems Analysis - The study complements available results on the existence of Nash equilibrium in resource extraction games with an arbitrary number of agents. It is assumed that...     

一类非规则并行应用问题的通信集生成算法

非规则计算是大规模并行应用中普遍存在和影响效率的关键问题.在基于分布式内存的数据并行范例中,如何针对非规则数组引用,有效地生成本地内存访问序列和通信集,是并行编译生成SPMD结点程序所必须解决的重要问题.文中针对两重嵌套循环中,下一层循环边界是上一层循环变量的线性或非线性函数,数组下标是两层循环变量的非线性函数这样一类包含非规则数组引用的并行应用问题,提出了一种在编译时生成通信集的代数算法.并且针对cyclic(k)数据分布和线性对齐模板,借助整数格概念,给出了编译时全局地址和本地地址之间的转换方法.文中还给出了相应的经过通信优化的SPMD结点程序.最后通过实例验证了算法的正确性.该算法的意义在于避免了传统Inspector/Executor非规则计算模型中的Inspector阶段,从而节省了运行时Inspector阶段通过穷举下标生成通信集的巨大开销.     

Special Feature: Microprocessor Assembly Language Draft Standard

Consolidating existing assembly language features, this proposed standard establishes assembly language conventions for present and future microprocessors. It is, offered here for public comment before submission to the IEEE Standards Board.     

面向航天器控制的专用语言及编译程序设计

针对陆基测控网测控站遥控操作模式不能适应新的测控需求以及国际测控合作的实际，提出了一种面向航天器操作的航天器控制语言（SCL语言）。该语言能够有效地解决航天器上行控制、参数判断和数据同步等航天器测控专用语句的设计难题，为航天器控制人员提供有力的工具。同时根据SCL语言的特点，提出了一种快速实现其编译程序的技术途径。给出了一种不同于一般高级语言特殊设计的实现方法。通过多颗同步和近地航天器测控实际应用，验证了SCL语言及编译程序的正确性，保证了陆基测控网实现了对卫星的闭环测控，极大提高了航天器的控制效率。