Quotient Complexity of Closed Languages

A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in an analogous way, where by factor we mean contiguous subsequence, and by subword we mean scattered subsequence. We study the state complexity (which we prefer to call quotient complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star, and reversal in each of the four classes of closed languages. We show that repeated applications of positive closure and complement to a closed language result in at most four distinct languages, while Kleene closure and complement give at most eight.     

Palindrome words and reverse closed languages

A word which is equal to its mirror image is called a palindrome word. Any language consisting of palindrome words is called a palindrome language. In this paper we investigate properties of palindrome words and languages. We show that there is no dense regular language consisting of palindrome words. A language contains all the mirror images of its elements is called a reverse closed language. Clearly, every palindrome language is reverse closed. We show that whether a given regular or context-free language is reverse closed is decidable. We study certain properties concerning reverse closed finite maximal prefix codes in this paper. Properties of languages that commute with reverse closed languages are investigated too.     

Decidability of operation problems for T0L languages and subclasses

We investigate the decidability of the operation problem for T0L languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (0L languages, T0L languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of 0L and T0L languages and their propagating variants are not even semidecidable. The situation changes for unary 0L languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable.     

(DNA) computing by carving

 Inspired by the experiments reported recently in the emerging area of DNA computing, we consider a somewhat unusual type of a computation strategy: generate a (large) set of candidate solutions of a problem, then remove the non-solutions such that what remains is the set of solutions. We call this a computation by carving. This leads both to a speculation with possible important consequences and to interesting theoretical computer science (formal language) questions. The speculation is that in this way we can “compute” non-recursively enumerable languages, because the family of recursively enumerable languages is not closed under complementation. The formal language theory questions concern sequences of languages with certain regularities, needed as languages to be extracted from the total language of candidate solutions of a problem. Specifically, we consider sequences of languages obtained by starting from a given regular language and iteratively applying to it a given finite state sequential transducer (a gsm). Computing by carving with respect to such a sequence of languages can identify all context-sensitive languages and can also lead to non-recursively enumerable languages (but not all recursively enumerable languages can be obtained in this way). In practical circumstances, the carving process should be finite, hence, in general, approximations of the desired language are obtained. We also briefly discuss this aspect.     

Cônes rationnels commutatifs

We study full trios generated by commutative languages. We give, for instance, a necessary and sufficient condition for a commutative language to be erasable. This allows us to show that slip commutative languages are erasable. We prove also the existence, in the family of nonrational commutative languages, of a minimal language for rational transductions.     

Learning regular languages using RFSAs

Residual languages are important and natural components of regular languages and several grammatical inference algorithms naturally rely on this notion. In order to identify a given target language L, classical inference algorithms try to identify words which define identical residual languages of L. Here, we study whether it could be interesting to perform a tighter analysis by identifying inclusion relations between the residual languages of L. We consider the class of Residual Finite State Automata (RFSAs). An RFSA A is a NonDeterministic Automaton whose states corresponds to residual languages of the language L_A it recognizes. The inclusion relations between residual languages of L_A can be naturally materialized on A. We prove that the class of RFSAs is not polynomially characterizable. We lead some experiments which show that when a regular language is randomly drawn by using a nondeterministic representation, the number of inclusion relations between its residual languages is very important. Moreover, its minimal RFSA representation is much smaller than its minimal DFA representation. Finally, we design a new learning algorithm, DeLeTe2, based on the search for the inclusion relations between the residual languages of the target language. We give sufficient conditions for the identifiability of the target language. We experimentally compare the performance of DeLeTe2 to those of classical inference algorithms.     

Some Properties of Iterated Languages

A special kind of substitution on languages called iteration is presented and studied. These languages arise in the application of semantic automata to iterations of generalized quantifiers. We show that each of the star-free, regular, and deterministic context-free languages are closed under iteration and that it is decidable whether a given regular or determinstic context-free language is an iteration of two such languages. This result can be read as saying that the van Benthem/Keenan ‘Frege Boundary’ is decidable for large subclasses of natural language quantifiers. We also determine the state complexity of iteration of regular languages.     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.     

Bi-catenation and shuffle product of languages

The shuffle product of two words consists of all words obtained by inserting one word into another word sparsely. The shuffle product of two languages is the union of all the shuffle products of two words taken one from each of these two languages. The bi-catenation of two languages A andB is the set . A non-empty word which is not a power of any other word is called a primitive word. A language is a prefix code if no word in this language is a prefix of any other word in this language. This paper is devoted to the investigation of the elementary properties of bi-catenation and shuffle product of languages. The families of prefix codes, disjunctive languages and languages consisting of primitive words with respective to these two operations are studied. We characterize languages of which the bi-catenation or the shuffle product with any non-empty word are prefix codes. We also derive that for any bifix code A, both and , , are disjunctive languages, where Q is the set of all primitive words over an alphabet X with more than one letter and . For the shuffle product case, surprisingly is a regular language, where a is a letter of the alphabet X. Received: 22 September 1997 / 7 January 1998     

Büchi context-free languages

We define context-free grammars with Büchi acceptance condition generating languages of countable words. We establish several closure properties and decidability results for the class of Büchi context-free languages generated by these grammars. We also define context-free grammars with Müller acceptance condition and show that there is a language generated by a grammar with Müller acceptance condition which is not a Büchi context-free language.     

一种测试语言包含的算法

在积自动机基础上,利用互模拟关系引出商自动机,用以解决积自动机的状态组合爆炸问题。进而提出一个自然的测试语言包含的算法,这种算法的空间复杂度与规范自动机的状态目呈指数关系即O（2^k),其中K是规范自动机的状态数目。     

The Appropriateness of Predicate Invention as Bias Shift Operation in ILP

The task of predicate invention in Inductive Logic Programming is to extend the hypothesis language with new predicates if the vocabulary given initially is insufficient for the learning task. However, whether predicate invention really helps to make learning succeed in the extended language depends on the language bias currently employed.In this paper, we investigate for which commonly employed language biases predicate invention is an appropriate shift operation. We prove that for some restricted languages predicate invention does not help when the learning task fails and we characterize the languages for which predicate invention is useful. We investigate the decidability of the bias shift problem for these languages and discuss the capabilities of predicate invention as a bias shift operation.     

Implementation of visual languages using pattern‐based specifications

The implementation of visual languages requires a wide range of conceptual and technical knowledge from issues of user interface design and graphical implementation to aspects of analysis and transformation for languages in general. We present a powerful toolset that incorporates such knowledge. Our toolset generates editors from high‐level specifications. A language is specified by identifying certain patterns in the language structure and selecting a visual representation from a set of precoined solutions. Visual programs are represented by attributed abstract trees. Therefore, further phases of processing visual programs can be generated by state‐of‐the‐art tools for language implementation. We demonstrate that even challenging visual languages can be implemented with reasonably little effort and with rather limited technical knowledge. The approach is suitable for a large variety of visual language styles. Copyright © 2003 John Wiley & Sons, Ltd.     

One application of real-valued interpretation of formal power series

We define two natural properties of context-free grammars. The first property generalizes linearity and the second property strengthens nonlinearity. A language generated by an unambiguous grammar of the first type is called the language with weak linear structure and a language generated by an unambiguous grammar of the second type is called the language with strong nonlinear structure. Our main theorem states that the family of unambiguous grammars generating languages with weak linear structure and the family of unambiguous grammars generating languages with strong nonlinear structure are effectively separable.     

Heuristic search in PARLOG using replicated worker style parallelism

Most concurrent logic programming languages hide the distribution of processes among physical processors from the programmer. For parallel applications based on heuristic search, however, it is important for the programmer to accurately control this distribution. With such applications, an inferior distribution strategy easily leads to enormous search overheads, thus decreasing speedup on parallel hardware.

To solve this problem, various language extensions for concurrent logic languages have been proposed, such as mapping notations and priorities. We present an alternative approach that does not require any new language features. Our solution is to use the replicated workers paradigm in a concurrent logic language (PARLOG). This paradigm has thus far mainly been used in parallel procedural languages, such as Linda and Orca. We show that it is just as useful for logic languages. We have implemented two parallel applications, the Traveling Salesman Problem and alpha-beta search, using this approach. Also, we have done some performance measurements of these programs on a multiprocessor. These experiments show that significant speedups can be obtained in this way.     

Design dysphasia and the pattern maintenance cycle

Software developers utilize design methods that enable them to manipulate conceptual structures that correlate to programming language features. However, programming languages and the programming paradigms they embody co-evolve over time. Within industrial and academic circles, for example, object-oriented programming has evolved and effectively replaced imperative programming. More recently, many object-oriented languages have assimilated features from other programming paradigms, evolving into multiparadigm languages we refer to as ‘object-oriented plus–plus’ or OO++. This language evolution may weaken the interface between design and implementation, introducing what we call ‘design dysphasia’—a partial disability in the use of a programming language because of incongruous design methods. Software design patterns capture elements of reusable design within a specific context. When the programming languages that are part of pattern context evolve, patterns must adapt to the language change or they may reinforce design dysphasia in the practitioner. We assert that the current ‘capture/recapture’ pattern maintenance model is suboptimal for adapting patterns to language evolution and propose a new ‘capture/modify/recapture’ maintenance cycle as a more effective approach. We then suggest a concrete ‘modify’ phase for current patterns to be adapted to object-oriented based multiparadigm language trends. We present an OO++ Iterator pattern as an example throughout.