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.     

Quasi-realtime languages

The quasi-realtime languages are seen to be the languages accepted by nondeterministic multitape Turing machines in real time. The family of quasi-realtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. It is identical with the family of languages accepted by nondeterministic multitape Turing machines in linear time. Every quasi-realtime language can be accepted in real time by a nondeterministic one stack, one pushdown store machine, and can be expressed as the length-preserving homomorphic image of the intersection of three context-free languages.The research reported in this paper was announced at the ACM Symposium on the Theory of Computing, Marina del Rey, California, May, 1969. This research has been supported in part by Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-68-C-0029.     

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.     

The family of one-counter languages is closed under quotient

Summary We study, first, the operation of quotient in connection with rational transductions. We show, afterwards, that Rocl, the family of one counter languages is closed under quotient by a context-free language. On the contrary, every recursively enumerable language is the quotient of two linear languages.     

On the intersection of regex languages with regular languages

In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.     

On iterated hairpin completion

(Bounded) hairpin completion and its iterated versions are operations on formal languages which have been inspired by hairpin formation in DNA biochemistry. The paper answers two questions asked in the literature about iterated hairpin completion.The first question is whether the class of regular languages is closed under iterated bounded hairpin completion. Here we show that this is true by providing a more general result which applies to all classes of languages which are closed under finite union, intersection with regular sets, and concatenation with regular sets. In particular, all Chomsky classes and all standard complexity classes are closed under iterated bounded hairpin completion.In the second part of the paper we address the question whether the iterated hairpin completion of a singleton is always regular. In contrast to the first question, this one has a negative answer. We exhibit an example of a singleton language whose iterated hairpin completion is not regular: actually, it is not context-free, but context-sensitive.     

On languages of automaton counter machines

A class of formal languages (ACML) acceptable by automaton counter machines is considered. This class is shown to be close with respect to the operations of union, regular intersection, concatenation, infinite iteration, homomorphism, and inverse homomorphism. It follows from here that this class is a full abstract family of languages [7] with all the properties following from this. Furthermore, the ACML is close with respect to intersection and substitution but is not closed with respect to complement and reverse. For the ACML class, the problems of emptiness and recognition of words of a language given by an automaton counter machine are decidable, but the problems of inclusion and equivalence of languages are undecidable. A comparison with other classes of languages (regular, context-free, context-sensitive, and Petri-net languages) is performed.     

2DST mappings on languages and related problems

Let $\text{l}$ be a family of languages effectively closed under inverse homomorphism and intersection with regular sets and such that the languages have effectively constructible semilinear Parikh maps. We show that there is an algorithm to decide given a language L in $\text{L}$ and a language R accepted by a one-way nondeterministic multicounter machine, where each counter makes exactly one reversal, whether L∩R is empty. This result has many applications. In particular, it can be used to show that there is an algorithm to decide given a language L in $\text{L}$ and two-way deterministic sequential transducers (2DST's) S₁ and S₂ whether S₁ and S₂ are equivalent on L.     

One-way acceptors and languages

In the present paper, a parallel presentation of the theories of abstract families of languages (AFL) and abstract families of deterministic languages (AFDL) is given. This is done by introducing two families of languages. One of them is the one-way nondeterministic family of languages (1NFL). A 1NFL is a family of languages closed under special marked substitution and inverse nondeterministic a-gsm mapping. The deterministic counterpart of 1NFL is 1DFL. It is shown that 1NFL and 1DFL are equivalent to AFL and AFDL, respectively. These families of languages are then used to characterize, side by side and with alternate proofs, the families of languages accepted by AFA and AFDA. Moreover, it is also shown that 1NFL and 1DFL can be used to characterize the families of languages accepted by a closed class of 1NBA and 1DBA, respectively.This work was supported in part by the University Research Council of Youngstown State University, Youngstown, Ohio.     

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.     

NTS languages are deterministic and congruential

A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove here that such grammars generate deterministic languages which are finite unions of congruence classes. Moreover, we show that this family of languages is closed under reversal and intersection with regular sets. A forthcoming paper will prove that, for this class, the equivalence problem is decidable.     

Characterization of co-observable languages and formulas for their super/sublanguages

We present fixed-point based characterization of several classes of co-observable languages that are of interest in the context of decentralized supervisory control of discrete-event systems, including C&P /spl or/ D&A co-observable languages, C&P co-observable languages, and D&A co-observable languages. We also provide formulas for computing super/sublanguages for each of these classes. In cases where the class of co-observable languages is not closed under intersection/union, we provide upper/lower bound of the super/sublanguage formula we present. The computation of super/sublanguages and also computation of their upper/lower bounds has lead to the introduction of other classes of co-observable languages, namely, strongly C&P co-observable languages, strongly D&A co-observable languages, locally observable languages, and strongly locally observable languages. Fixed-point based characterization of all the above language classes is also given, and their closure under intersection/union is investigated. We also study whether the fixed-point operator preserves prefix closure, relative closure (also called L/sub m/(G)-closure), and controllability.     

Fuzzy multiset finite automata and their languages

Inspired by the generalizations from grammars and finite automata to fuzzy grammars and fuzzy finite automata, respectively, we introduce the concepts of fuzzy multiset grammars and fuzzy multiset finite automata (FMFAs), as the generalizations of multiset grammars and multiset finite automata, respectively. The relationship between fuzzy multiset regular grammars and FMFAs is discussed. Furthermore, we define some operations on fuzzy multiset languages, and prove that the family of FMFA languages is closed under the operations.     

The Boolean closure of linear context-free languages

Closures of linear context-free languages under Boolean operations are investigated. The intersection closure and the complementation closure are incomparable. By closing these closures under further Boolean operations we obtain several new language families. The hierarchy obtained by such closures of closures is proper up to a certain level, where it collapses to the Boolean closure which, in turn, is incomparable with several closures of the family of context-free languages. The Boolean closure of the linear context-free languages is properly contained in the Boolean closure of the context-free languages. A characterization of a class of non-unary languages that cannot be expressed as a Boolean formula over the linear context-free languages is presented.     

A decidability result for deterministic ω context-free languages

It is shown that the problem whether an effectively given deterministic ω-context-free language is in the family of all closures of deterministic context-free languages is decidable.     

Algebraic properties on the cuts of lattice-valued regular languages

In this paper, the algebraic operations on the cuts of lattice-valued regular languages are studied. Some sufficient conditions are given to guarantee the family of the cuts of lattice-valued regular languages to be closed under such algebraic operations as union, intersection, complement, quotient, homomorphism, inverse homomorphism, concatennation, reversal, etc. This work is supported by National Science Foundation of China (Grant No.10571112), “TRAPOYT” of China and National 973 Foundation Research Program (Grant No. 2002CB312200).     

Strategical languages of infinite words

We deal in this paper with strategical languages of infinite words, that is those generated by a nondeterministic strategy in the sense of game theory. We first show the existence of a minimal strategy for such languages, for which we give an explicit expression. Then we characterize the family of strategical languages as that of closed ones, in the topological space of infinite words. Finally, we give a definition of a Nash equilibrium for such languages, that we illustrate with a famous example.     

Decision problems for convex languages

We examine decision problems for various classes of convex languages, previously studied by Ang and Brzozowski, originally under the name “continuous languages”. We can decide whether a language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but these problems become PSPACE-complete if L is represented by an NFA. If a regular language is not convex, we find tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages. Finally, we briefly examine these questions where L is represented by a context-free grammar.     

A history of data-flow languages

Data-flow refers both to a language-level paradigm of computation and to a family of processor architectures based on this paradigm. This article elaborates data-flow language issues and the evolution of data-flow languages. In considering limits to the expressive power of these languages, underlying architectural issues are discussed. Although the article attempts to present a complete history of data-flow languages, it concentrates on those languages that specifically belong to this class and have been implemented for a data-flow machine. In many cases, the distinctions between issues of language semantics and machine architecture are unclear. Usually we have found that this reflects the evolution of data-flow, and the close association between language and architecture development. In some sections of the article, it may appear that there is an imbalance in the amount of detail presented when compared with other sections. This imbalance is proportional to the publications and the amount of information readily available for the topics     

On the complexity of the instance checking problem in concept languages with existential quantification

Most of the work regarding complexity results for concept languages consider subsumption as the prototypical inference. However, when concept languages are used for building knowledge bases including assertions on individuals, the basic deductive service of the knowledge base is the so-called instance checking, which is the problem of checking if an individual is an instance of a given concept. We consider a particular concept language, calledALE, and we address the question of whether instance checking can be really solved by means of subsumption algorithms in this language. Therefore, we indirectly ask whether considering subsumption as the prototypical inference is justified. Our analysis, carried out considering two different measure of complexity, shows that inALE instance checking is strictly harder than subsumption. This result singles out a new source of complexity in concept languages, which does not show up when checking subsumption between concepts.This work has been supported by the ESPRIT Basic Research Action N.6810-COMPULOG 2 and by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the CNR (Italian Research Council).