P-hardness of the emptiness problem for visibly pushdown languages

Visibly pushdown languages form a subclass of the context-free languages which is appealing because of its nice algorithmic and closure properties. Here we show that the emptiness problem for this class is not any easier than the emptiness problem for context-free languages, namely hard for deterministic polynomial time. The proof consists of a reduction from the alternating graph reachability problem.     

Practical compressed string dictionaries

The need to store and query a set of strings – a string dictionary – arises in many kinds of applications. While classically these string dictionaries have accounted for a small share of the total space budget (e.g., in Natural Language Processing or when indexing text collections), recent applications in Web engines, Semantic Web (RDF) graphs, Bioinformatics, and many others handle very large string dictionaries, whose size is a significant fraction of the whole data. In these cases, string dictionary management is a scalability issue by itself. This paper focuses on the problem of managing large static string dictionaries in compressed main memory space. We revisit classical solutions for string dictionaries like hashing, tries, and front-coding, and improve them by using compression techniques. We also introduce some novel string dictionary representations built on top of recent advances in succinct data structures and full-text indexes. All these structures are empirically compared on a heterogeneous testbed formed by real-world string dictionaries. We show that the compressed representations may use as little as 5% of the original dictionary size, while supporting lookup operations within a few microseconds. These numbers outperform the state-of-the-art space/time tradeoffs in many cases. Furthermore, we enhance some representations to provide prefix- and substring-based searches, which also perform competitively. The results show that compressed string dictionaries are a useful building block for various data-intensive applications in different domains.     

Feedback automata and their languages

We introduce families of languages which are generated by deterministic and nondeterministic feedback-controlled models of automata. In case of the two deterministic models considered, the generated families are proper subclasses of the family of regular languages, where, in case of the nondeterministic model, the generated family equals the family of ?-free regular languages.     

Shuffle languages are in P

In this paper we show that shuffle languages are contained in one-way-NSPACE(log n) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression E we construct a shuffle automaton which accepts the language generated by E and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.     

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.     

Hybrid languages

Hybrid languages have both modal and first-order characteristics: a Kripke semantics, and explicit variable binding apparatus. This paper motivates the development of hybrid languages, sketches their history, and examines the expressive power of three hybrid binders. We show that all three binders give rise to languages strictly weaker than the corresponding first-order language, that full first-order expressivity can be gained by adding the universal modality, and that all three binders can force the existence of infinite models and have undecidable satisfiability problems.     

A non-learnable class of E-pattern languages

We investigate the inferrability of E-pattern languages (also known as extended or erasing pattern languages) from positive data in Gold's learning model. As the main result, our analysis yields a negative outcome for the full class of E-pattern languages—and even for the subclass of terminal-free E-pattern languages—if the corresponding terminal alphabet consists of exactly two distinct letters. Furthermore, we present a positive result for a manifest subclass of terminal-free E-pattern languages. We point out that the considered problems are closely related to fundamental questions concerning the nondeterminism of E-pattern languages.     

A note on equations for commutative regular languages

In this note we prove that the equations satisfied by one-letter regular languages are exactly those satisfied by commutative regular languages. This answers a problem raised by Arto Salomaa.     

Langford strings,formal languages and contextual ambiguity

We propose a series of generalizations of Langford strings considered in Combinatorics and discuss the place of the corresponding languages in Chomsky hierarchy, as well as their contextual ambiguity in the sense of algebraic linguistics.     

Equality sets of prefix morphisms and regular star languages

We consider equality sets of prefix morphisms, that is, sets E(g₁,g₂)={w|g₁(w)=g₂(w)}, where g₁ and g₂ are prefix morphisms. Recall that a morphism g is prefix if, for all different letters a and b, g(a) is not a prefix of g(b). We prove a rather surprising equality on families of languages, namely, that the family of regular star languages coincides with the family of languages of form πA(E(g₁,g₂)) for some prefix morphisms g₁ and g₂, and a projection πA which deletes the letters not in A.     

Learning multiple languages in groups

We consider a variant of Gold’s learning paradigm where a learner receives as input n$n$ different languages (in the form of one text where all input languages are interleaved). Our goal is to explore the situation when a more “coarse” classification of input languages is possible, whereas more refined classification is not. More specifically, we answer the following question: under which conditions, a learner, being fed n$n$ different languages, can produce m$m$ grammars covering all input languages, but cannot produce k$k$ grammars covering input languages for any k>m$k>m$. We also consider a variant of this task, where each of the output grammars may not cover more than r$r$ input languages. Our main results indicate that the major factor affecting classification capabilities is the difference n−m$n-m$ between the number n$n$ of input languages and the number m$m$ of output grammars. We also explore the relationship between classification capabilities for smaller and larger groups of input languages. For the variant of our model with the upper bound on the number of languages allowed to be represented by one output grammar, for classes consisting of disjoint languages, we found complete picture of relationship between classification capabilities for different parameters n$n$ (the number of input languages), m$m$ (number of output grammars), and r$r$ (bound on the number of languages represented by each output grammar). This picture includes a combinatorial characterization of classification capabilities for the parameters n,m,r$n,m,r$ of certain types.     

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.     

Systems implementation languages and IRONMAN

The U.S. Department of Defense has recently issued a set of requirements, which it called IRONMAN, for the design of a programming language that it will use for embedded computer applications. To date four competing languages have been designed and, after considerable debate and scrutiny, these have been reduced to two. It is expected that the winning language will be selected during 1979. This report compares the IRONMAN requirements against the state-of-the-art in systems implementation language design in an attempt to see the extent to which IRONMAN can be met from existing technology. Particular emphasis is given to the areas of large-scale program structuring, parallel programming, exception handling and hardware interaction. Finally, Dijkstra's criticism of IRONMAN and the competing languages will be examined. It will be argued that he may be justified in doubting the viability of a language with such diverse features.     

A framework to visualize equivalences between computational models of regular languages

We discuss how to increase and simplify the understanding of the equivalence relations between machine models and/or language representations of formal languages by means of the animation tool SAGEMoLiC. Our new educational tool permits the simulation of the execution of models of computation, as many other animation systems do, but its philosophy goes further than these of the usual systems since it allows for a true visualization of the key notions involved in the formal proofs of these equivalences. In contrast with the proposal of previous systems, our approach to visualize equivalence theorems is not a simple “step by step animation” of specific conversion algorithms between computational models and/or grammatical representations of formal languages, because we make emphasis on the key theoretical notions involved in the formal proofs of these equivalences.     

Kernel methods for learning languages

This paper studies a novel paradigm for learning formal languages from positive and negative examples which consists of mapping strings to an appropriate high-dimensional feature space and learning a separating hyperplane in that space. Such mappings can often be represented flexibly with string kernels, with the additional benefit of computational efficiency. The paradigm inspected can thus be viewed as that of using kernel methods for learning languages.     

The equality of EOL languages and codings of ol languages

It is proved that a language is a coding (a letter-to-letter homomorphism) of a OL language, if, and only if, it is an EOL language.     

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.     

Kleene modules and linear languages

A Kleene algebra (K, +, ·, *, 0, 1) is an idempotent semiring with an iteration * as axiomatised by Kozen. We consider left semiring modules (A, +, 0, :) over Kleene algebras. We call such a left semiring module a Kleene module if each linear equation x = a + r : x has a least solution, where : is the product from K × A to A. The linear context-free languages can be viewed as a Kleene module A over a Kleene algebra R of binary regular word relations. Thus, the simultaneous linear fixed-point operator μ on languages can be reduced to iteration * on R and the scalar product :.