The membership and equivalence problems for picture languages

The paper describes two principal results: (1) there is a nondeterministic polynomial-time algorithm to determine whether an arbitrary picture is a member of a context-free picture language and (2) the equivalence problem for regular picture languages is not decidable (not even partially decidable). This solves open questions described in earlier publications. Furthermore, these results are best possible. That is, the membership problem for context-free picture languages was earlier shown to be NP-hard and the complement of the equivalence problem for regular picture languages is easily seen to be partially decidable.     

Pseudo-inversion: closure properties and decidability

We consider a pseudo-inversion operation inspired by biological events, such as DNA sequence transformations, where only parts of a string are reversed. We define the pseudo-inversion of a string \(w = uxv\) to be the set of all strings \(v^Rxu^R\), where \(uv \ne \lambda \) and consider the operation from a formal language theoretic viewpoint. We show that regular languages are closed under the pseudo-inversion operation whereas context-free languages are not. Furthermore, we study the iterated pseudo-inversion operation and show that the iterated pseudo-inversion of a context-free language is recognized by a nondeterministic reversal-bounded multicounter machine. Finally, we introduce the notion of pseudo-inversion-freeness and examine closure properties and decidability problems for regular and context-free languages. We demonstrate that pseudo-inversion-freeness is decidable in polynomial time for regular languages and undecidable for context-free languages.     

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.     

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.     

Look-ahead on pushdowns

The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the non-deterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look-ahead on the input, and LL-regular iterated indexed grammars.     

The covering problem for linear context-free grammars

Language equivalence, grammatical covering and structural equivalence are all notions of similarity defined on context-free grammars. We show that the problem of determining whether an arbitrary linear context-free grammar covers another is complete for the class of languages accepted by polynomially space bounded Turing machines. We then compare the complexity of this problem with the analogous problems for language equivalence and structural equivalence, not only for linear grammars, but also for regular grammars and unrestricted context-free grammars. As a step in obtaining the main result of this paper, we show that the equivalence problem for linear s-grammars is decidable in polynomial time.     

Timing Diagrams: Formalization and Algorithmic Verification

Timing diagrams are popular in hardware design. They have been formalized for use in reasoning tasks, such as computer-aided verification. These efforts have largely treated timing diagrams as interfaces to established notations for which verification is decidable; this has restricted timing diagrams to expressing only regular language properties. This paper presents a timing diagram logic capable of expressing certain context-free and context-sensitive properties. It shows that verification is decidable for properties expressible in this logic. More specifically, it shows that containment of -regular languages generated by Büchi automata in timing diagram languages is decidable. The result relies on a correlation between timing diagram and reversal bounded counter machine languages.     

Characterizations of regular and context-free matrices

The u-v theorem for context-free languages is extended to prove an intercalation theorem for the family of context-free matrix languages. A row-wise iteration factor theorem is proved for the families of regular and context-free matrix languages. Characterizations of regular and context-free matrix languages are given in terms of vertical regular sequences and simple operations on vertical regular sequences. Closure of regular and context-free matrix languages under array nondeterministic finite state transducer mappings is established and an image theorem proved. This is used to give another characterization of regular matrix languages. Further it is shown that the family of regular matrix languages is a principal abstract family of matrices (AFM). The effect of string control and array control on these families are examined.     

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.     

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.     

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.     

语言附着的句法结构

本文研究语言Ｌ的附着Ａｄｈ（Ｌ）的句法结构，借助于Ｌ的语法分析树，我们分析了Ａｄｈ（Ｌ）的句法特征，提出并证明了正规语言和上下文无关语言附着的叠代定理，从而解决了这两类语言的附着的句法结构问题。另外，应用引理证明了某些附着不是正规语言的附着或上下文无关语言的附着。     

Controlled bidirectional grammars

We investigate context-free grammars the rules of which can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. We distinguish several modes of derivation for this kind of grammar. The resulting language families (properly) extend the family of context-free languages. We establish some closure properties of these language families and some grammatical transformations which yield a few normal forms for this type of grammar. Finally, we consider some special cases (viz. the context-free grammar is linear or left-linear), and generalizations, in particular, the use of arbitrary rather than regular control languages.     

Leftist Grammars and the Chomsky Hierarchy

Leftist grammars are characterized in terms of rules of the form a → ba and cd → d, without distinction between terminals and nonterminals. They were introduced by Motwani et al. [13], where the accessibility problem for some general protection system was related to these grammars. This protection system was originally proposed in [4] and [15] in the context of Java virtual worlds. The accessibility problem is formulated in the form "Can object p gain (illegal) access to object q by a series of legal moves (as prescribed by the policy)?" The membership problem for leftist grammar is decidable [13], which implies decidability of the accessibility problem for the appropriate protection system. We study relationships between language classes defined by various types of leftist grammars and classes of the Chomsky hierarchy. We show that general leftist grammars can define languages which arenot context free, answering in the negative a question from [13]. Moreover, we study some restricted variants of leftist grammars and relate them to regular, deterministic context-free, and context-free languages.     

Infinite Convergent String-rewriting Systems and Cross-sections for Finitely Presented Monoids

A finitely presented monoid has a decidable word problem if and only if it can be presented by some left-recursive convergent string-rewriting system if and only if it has a recursive cross-section. However, regular cross-sections or even context-free cross-sections do not suffice. This is shown by presenting examples of finitely presented monoids with decidable word problems that do not admit regular cross-sections, and that, hence, cannot be presented by left-regular convergent string-rewriting systems. Also examples of finitely presented monoids with decidable word problems are presented that do not even admit context-free cross-sections. On the other hand, it is shown that each finitely presented monoid with a decidable word problem has a finite presentation that admits a cross-section which is a Church–Rosser language. Finally we address the notion of left-regular convergent string-rewriting systems that are tractable.     

Termination Proofs for String Rewriting Systems via Inverse Match-Bounds

Annotating a letter by a number, one can record information about its history during a rewrite derivation. In each rewrite step, numbers in the reduct are updated depending on the redex numbering. A string rewriting system is called match-bounded if there is a global upper bound to these numbers. Match-boundedness is known to be a strong sufficient criterion for both termination and preservation of regular languages. We show that the string rewriting systems whose inverse (left and right hand sides exchanged) is match-bounded, also have exceptional properties, but slightly different ones. Inverse match-bounded systems need not terminate; they effectively preserve context-free languages; their sets of normalizable strings and their sets of immortal strings are effectively regular. These languages can be used to decide the normalization, the uniform normalization, the termination and the uniform termination problem for inverse match-bounded systems. We also prove that the termination problem is decidable in linear time, and that a certain strong reachability problem is decidable, thereby solving two open problems of McNaughton’s. Like match-bounds, inverse match-bounds entail linear derivational complexity on the set of terminating strings.     

Inverse star, borders, and palstars

A language L is closed if L=L^?. We consider an operation on closed languages, L−?, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L−? is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free.     

On the language equivalence of NE star-patterns

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting (non-empty) strings for variables. The pattern languages are one of language family which is orthogonal to the Chomsky-type languages hierarchy. They have many applications, such as the extended regular expressions, for instance, in languages Perl, awk, etc. They are well applicable in machine learning as well. There are erasing and non-erasing patterns are used. For non-erasing pattern languages the equivalence of languages is decidable but the inclusion problem for them is undecidable. In extended regular expressions one can use union, concatenation and Kleene star to make more complex patterns. It is also known, that the equivalence problem of extended regular expressions is undecidable. However, the problem, whether the equivalence is decidable for patterns using only concatenation and star still open. In this paper there are some interesting results about inclusion properties and equivalences of some kinds of erasing and non-erasing pattern languages. We show that the equivalence problem of non-erasing patterns in some cases can be reduced to the decidability problem of some very special inclusion properties. These results may be useful to decide whether the language equivalence of non-erasing star-patterns is decidable or not.     

Decision problems concerning thinness and slenderness of formal languages

A language L is called thin if for almost all n there is at most one word of length n in L. A language L is called slender if there is a positive integer k such that for any n there are at most k words of length n in L. The notions of Parikh thin and Parikh slender languages are defined similarly by counting the words with the same Parikh vectors instead of the words of the same length. In this paper we discuss decision problems concerning these four properties. It is shown that all four properties are decidable for bounded semilinear languages but undecidable for DT0L languages. As a consequence all these problems are decidable for context-free languages. Received 9 June 1997 / 3 December 1997     

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.