On the subword complexity of m-free D0L languages

A word is called m-free (m ? 2) if it does not contain a subword of the form x^m where x is a nonempty word. A language is called m-free if it consists of m-free words only. The subword complexity of a language K, denoted π_K, is a function of positive integers which to each positive integer n assigns the number of different subwords of length n occuring in words of K. It is known that if a D0L language K is m-free for some m ? 2, then, for all n, π_K(n) ? qn log₂n for some positive integer q. We demonstrate that there exists a 3-free D0L language K on three letters such that, for all n ? n₀, π_K(n) ? rn log₂n for some positive real r and a positive integer n₀. We also demonstrate that if m ? 3 and K is an m-free D0L language on two letters, then, for all n, π_K(n) ? pn for some positive integer p.     

A remark on regularity of parallel languages

It is shown to be decidable of any given regular language R and FTOL language L, whether or not R = L     

Generalizing input-driven languages: Theoretical and practical benefits

Regular languages (RL) are the simplest family in Chomsky’s hierarchy. Thanks to their simplicity they enjoy various nice algebraic and logic properties that have been successfully exploited in many application fields. Practically all of their related problems are decidable, so that they support automatic verification algorithms. Also, they can be recognized in real-time.Context-free languages (CFL) are another major family well-suited to formalize programming, natural, and many other classes of languages; their increased generative power w.r.t. RL, however, causes the loss of several closure properties and of the decidability of important problems; furthermore they need complex parsing algorithms. Thus, various subclasses thereof have been defined with different goals, spanning from efficient, deterministic parsing to closure properties, logic characterization and automatic verification techniques.Among CFL subclasses, so-called structured ones, i.e., those where the typical tree-structure is visible in the sentences, exhibit many of the algebraic and logic properties of RL, whereas deterministic CFL have been thoroughly exploited in compiler construction and other application fields.After surveying and comparing the main properties of those various language families, we go back to operator precedence languages (OPL), an old family through which R. Floyd pioneered deterministic parsing, and we show that they offer unexpected properties in two fields so far investigated in totally independent ways: they enable parsing parallelization in a more effective way than traditional sequential parsers, and exhibit the same algebraic and logic properties so far obtained only for less expressive language families.     

Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable

We prove that any propagating E0L system cannot generate the language {w#w|w∈{0,1}^?}$\{w\mathrm{\#}w|w\in {\{0,1\}}^{?}\}$. This result, together with some known ones, enables us to conclude that the flip-pushdown automata with k pushdown reversals, i.e., the pushdown automata with the ability to flip the pushdown, and E0L systems are incomparable. This result solves an open problem stated by Holzer and Kutrib in 2003.     

The Decidability of the Structural Congruence for Beta-binders

Beta-binders is a recent process algebra developed for modeling and simulating biological systems. As usual for process calculi, the semantic definition heavily relies on a structural congruence. The treatment of the structural congruence is essential for implementation. The proof of the decidability of this congruence, reported in this paper, is a first step towards implementations.     

The finiteness of synchronous,tabled picture languages is decidable

In the present paper, synchronous, tabled chain code picture systems based on Lindenmayer systems (sT0L system) are studied with respect to the finiteness of their picture languages. The finiteness is proved to be decidable. Additionally, a method is given for deciding whether or not an sT0L system generates a finite picture language.     

Decidability of infinite-state timed CCP processes and first-order LTL

The ntcc process calculus is a timed concurrent constraint programming (ccp) model equipped with a first-order linear-temporal logic (LTL) for expressing process specifications. A typical behavioral observation in ccp is the strongest postcondition (sp). The ntcc sp denotes the set of all infinite output sequences that a given process can exhibit. The verification problem is then whether the sequences in the sp of a given process satisfy a given ntcc LTL formula.

This paper presents new positive decidability results for timed ccp as well as for LTL. In particular, we shall prove that the following problems are decidable: (1) the sp equivalence for the so-called locally-independent ntcc fragment; unlike other fragments for which similar results have been published, this fragment can specify infinite-state systems, (2) verification for locally-independent processes and negation-free first-order formulae of the ntcc LTL, (3) implication for such formulae, (4) Satisfiability for a first-order fragment of Manna and Pnueli's LTL. The purpose of the last result is to illustrate the applicability of ccp to well-established formalisms for concurrency.     

Data-base management systems—Data models and query languages

Data-base management systems support three types of data model—hierarchic, network, and relational. Query facilities range from high-level, nonprocedural languages to host-language, coded procedures. Evaluation of DBMS for geoscience applications requires careful consideration of both these features.     

Constants and label-equivalence: A decision procedure for reflexive regular splicing languages

A structural characterization of reflexive splicing languages has been recently given in [P. Bonizzoni, C. De Felice, R. Zizza, The structure of reflexive regular splicing languages via Schützenberger constants, Theoretical Computer Science 334 (2005) 71-98] and [P. Bonizzoni, G. Mauri, Regular splicing languages and subclasses, Theoretical Computer Science 340 (2005) 349-363] showing surprising connections between long standing notions in formal language theory, the syntactic monoid and Schützenberger constant and the splicing operation.In this paper, we provide a procedure to decide whether a regular language is a reflexive splicing language, based on the above-mentioned characterization that is given in terms of a finite set of constants for the language. The procedure relies on the notion of label-equivalence that induces a finite refinement of the syntactic monoid of a regular language L. A finite set of representatives for label-equivalent classes of constant words in L is defined and it is proved that such a finite set provides the splice sites of splicing rules generating language L.     

空间逻辑的一个定义框架及其可判定性

空间逻辑作为一个模态逻辑,能很好地描述分布式系统的行为和空间属性。其中,逻辑公式的有效性、可满足性及模型检测问题的可判定性已经得到广泛的研究。本文即是关于空间逻辑可判定性的一个综述,为此首先提出一个空间逻辑的定义框架,据此可以构造各种空间逻辑,并对它们的可判定性进行考察,从而指出影响空间逻辑的可判定性的关键因素。     

Ergonomic considerations in the design of interactive languages for process control

The paper introduces the concept of software ergonomics and stresses the importance of respecting the working habits of the user while designing the software aids. Language design criteria are presented under two broad categories: those involving the syntax of the language and those involving its semantics. These criteria are then exemplified using an actual experience of designing an interactive language (TOOL) for a large public utility.     

A class of high level languages for process control

An abstract notational system can serve as a model for the investigation of high level programming languages that explicitly support the monitoring and control of parallel events, provide data types at the bit level and allow real-time interaction between user and process. Run-time mechanisms that support the execution of programs in the notational system chosen on specific hardware can also be identified. A software tools environment can be designed to provide high level languages and runtime support for process control in a way that encourages portability among different hardware configurations.     

Integration of object-oriented programming languages and database systems in KOPERNIK

KOPERNIK is an object-oriented database system, that allows uniform specification of database requests and application programs. The user interface is based on Smalltalk, and the object-oriented data model is represented in terms of classes and messages. Techniques are discussed for implementing such a model on top of an underlying relational database system. Those parts of application programs that cannot be translated into a relational language are handled by a Smalltalk processor. The semantics of the database requests is defined in terms of a meta-model and meta-messages, using an object-oriented approach. Hence we derive rules for translation of database requests into SQL queries over a binary relational view, introduced as an intermediate level between the underlying database and our conceptual view.