Search

We survey our current knowledge of circuit complexity of regular languages. We show that regular languages are of interest as languages providing understanding of different circuit classes. We also prove that regular languages that are in AC0and ACC0are all computable by almost linear size circuits, extending the result of Chandra et al.[5].

This paper investigates the complexity of verbal languages and pattern languages of Thurston automatic groups in terms of the Chomsky hierarchy. Here the language generated by a pattern is taken as the set of representatives of all strings obtained when chosing values for the various variables. For noncommutative free groups, it is shown that the complexity of the verbal and pattern languages (in terms of level on the Chomsky hierarchy) does not depend on the Thurston automatic representation and that verbal languages cannot be context-free (unless they are either the empty word or the full group). They can however be indexed languages. Furthermore, it is shown that in the general case, it might depend on the exactly chosen Thurston automatic representation which level a verbal language takes in the Chomsky hierarchy. There are examples of groups where, in an appropriate representation, all pattern languages are regular or context-free, respectively.

In this chapter we introduce the first-order languages. They obey simple, clear formation rules. In later chapters we shall discuss whether, and to what extent, all mathematical propositions can be formalized in such languages.

In this paper the concept of Parikh-reducing Church–Rosser systems is studied. It is shown that for two classes of regular languages there exist such systems which describe the languages using finitely many equivalence classes of the rewriting system. The two classes are: 1.) the class of all regular languages such that the syntactic monoid contains only abelian groups and 2.) the class of all group languages over a two-letter alphabet. The construction of the systems yield a monoid representation such that all subgroups are abelian. Additionally, the complexity of those representations is studied.

A new type of graph is introduced, the grammar graph. The possibility of assigning labels to each node in such a graph extends it to the grammar net. The grammar net should be considered as a new graphical tool that helps in an analysis of whether a particular sentence belongs to a given context-sensitive grammar. Another concept, the derivation net, closely related to the grammar graph and of a similar structure, will be used to show an algorithm that is able to decide that some sentences do not belong to a language generated by a context sensitive grammar, while leaving others as a candidate members of it.

This article determines two learning-theoretic combinatorial parameters, the teaching dimension and the recursive teaching dimension, for various families of pattern languages over alphabets of varying size. Our results and formal proofs are of relevance to recent studies in computational learning theory as well as in formal language theory. This is an expanded and corrected version of an earlier paper by Mazadi et al. (2014).

We address the problem of providing a Borel-like classification of languages of infinite Mazurkiewicz traces, and provide a solution in the framework of ω -automata over infinite words – which is invoked via the sets of linearizations of infinitary trace languages. We identify trace languages whose linearizations are recognized by deterministic weak or deterministic Buchi (word) automata. We present a characterization of the class of linearizations of all recognizable ω -trace languages in terms of Muller (word) automata. Finally, we show that the linearization of any recognizable ω -trace language can be expressed as a Boolean combination of languages recognized by our class of deterministic Buchi automata.

We show that the information rate of the language accepted by a reversal-bounded deterministic counter machine is computable. For the nondeterministic case, we provide computable upper bounds. For the class of languages accepted by multi-tape deterministic finite automata, the information rate is computable as well.

The full scan condition on a language L introduced in [1] ensures that a word w must be completely inspected in order to decide whether or not w lies in L. We strengthen the condition by replacing the factor words in that definition by single letters. After examining the general case for both arbitrary and regular languages, we investigate the two-letter alphabet to find a complete description of the corresponding languages, which may be coded as infinite binary strings. Regularity of these languages corresponds to the associated numbers being rational and we find the minimal automata in all cases, which may be pictured as a cylinder of tape with a protruding end, although this cylinder is replaced by a Mobius strip for a special class of rational languages.

We investigate chop operations, which can be seen as generalized concatenation. For several language families of the Chomsky hierarchy we prove (non)closure properties under chop operations and incomparability to the family of languages that are the chop of two regular languages. We also prove non-closure of that language family under Boolean operations and closure under reversal. Further, the representation of a regular language as the chop of two regular expressions can be exponentially more succinct than its regular expression. By considering the chop of two linear context-free languages we already obtain language families that have non-semi-decidable problems such as emptiness or finiteness.

Complexity theory and the theory of regular languages both belong to the branch of computer science where the use of resources in computing is the main focus. However, they operate at different levels. While complexity theory seeks to classify computational problems by resource use, such as space and time, regular language theory remains at the very base of this hierarchy and is concerned with classes of computational problems for which membership is (potentially) decidable.

International audience; A regular language is lookahead (resp. block) deterministic if it is specified by a lookahead (resp. block) deterministic regular expression. These two subclasses of regular languages have been respectively introduced by Han and Wood for lookahead determinism and by Giammarresi et al. for block determinism, as a possible extension of one-unambiguous languages defined and characterized by Brüggemann-Klein and Wood.In this paper, we study the hierarchies and inclusion links of these families. We first show that each block deterministic language is the alphabetical image of some one-unambiguous language. Moreover, we show that deciding the block determinism of a regular language from its minimal DFA does not only require state elimination. Han and Wood state that there is a proper hierarchy in block deterministic languages, but prove it using this erroneous requirement. However, we prove their statement by giving our own parametrized family. We also prove that there is a proper hierarchy in lookahead deterministic languages by studying particular properties of unary regular expressions. Finally, using our valid results, we confirm that the family of block deterministic languages is strictly included in the one of lookahead deterministic languages by showing that any block deterministic unary language is one-unambiguous.

The expressive capacity of three different types of regular expressions without concatenation is studied. In particular, we consider alphabetic concatenation-free expressions, which are ordinary regular expressions without concatenation, simple concatenation-free expressions, where the set of literals is a finite set of words instead of letters, and concatenation-free expressions, where additionally complementation operations are possible. Characterizations of the corresponding language classes are obtained. In particular, a characterization of unary concatenation-free languages by the Boolean closure of certain sets of languages is shown. The characterizations are then used to derive a strict hierarchy that is, in turn, strictly included in the family of regular languages. The closure properties of the families are investigated. Furthermore, the position of the family of concatenation-free languages in the subregular hierarchy is considered and settled for the unary case. In particular, there are concatenation-free languages that do not belong to any of the families in the hierarchy. Moreover, except for comets, all the families considered in the subregular hierarchy are strictly included in the family of concatenation-free languages.

In this article, we summarize some new results on r-disjunctive languages and its related topics from some papers, these results form a new progress in this research area. In these results, we show the use of syntactic congruences (resp. syntactic monoids) of languages and the infix languages of languages in studying the characteristics, the decompositions and the classifications of the r-disjunctive languages. In addition, we set out some open problems in this area proposed in these papers.

Supporters of languages planned for international communication, like Esperanto, often claim that these languages are less complex and therefore easy to learn as compared to natural languages. To what extent does this claim have empirical support? In this contribution, planned languages will be presented from the perspective of learnability. In particular, the question of language complexity will be addressed. Almost all planned languages show a high degree of morphological regularity, obtained by a drastic reduction of allomorphy and suppletion. While these morphological traits can help learners acquire the basics of the planned language more easily as compared to standard natural languages, other factors should be taken into account in order to assess the learnability of these languages, in particular their sociolinguistic status.

The terminal-free pattern languages are not closed under most standard operations.We achieve even stronger results for union and intersection of these languages.Some of these results cease to hold if patterns with terminal symbols are considered.We characterise unions of two NE-pattern languages that are an E-pattern language.We characterise all unions of E-pattern languages that are an NE-pattern language. Pattern languages are a well-established class of languages, but very little is known about their closure properties. In the present paper we establish a large number of closure properties of the terminal-free pattern languages, and we characterise when the union of two terminal-free pattern languages is again a terminal-free pattern language. We demonstrate that the equivalent question for general pattern languages is characterised differently, and that it is linked to some of the most prominent open problems for pattern languages. We also provide fundamental insights into a well-known construction of E-pattern languages as unions of NE-pattern languages, and vice versa.

A deque automaton is a finite-state machine equipped with a deque memory tape. Such memory being more general than a queue or two stacks, we restrict consideration to quasi-real-time deque machines, for which we present useful normal forms. The closure properties of deque languages qualify them as an abstract family of languages but not a full one. The newly defined characteristic deque language CDL combines Dyck and AntiDyck (or FIFO) languages, and homomorphically characterizes the deque languages. The notion of deque graph from the graph drawing theory, well represents deque computations by means of a planar graph developed on a cylinder surface, with edges visualizing how deque symbols are inserted and removed. The drawing of deque computations on a cylinder is remindful of 3D models used in theoretical (bio)chemistry. We prove that a CDL can be defined in different ways: by a simple deque automaton, by labeled deque graphs, by cancellation rules, and by means of the shuffle and intersection of simpler languages. The labeled deque graph represents the syntax structure of a word.

The Tier-based Strictly 2-Local (TSL2) languages are a class of formal languages which have been shown to model long-distance phonotactic generalizations in natural language (Heinz et al., 2011). This paper introduces the Tier-based Strictly 2-Local Inference Algorithm (2TSLIA), the first nonenumerative learner for the TSL2 languages. We prove the 2TSLIA is guaranteed to converge in polynomial time on a data sample whose size is bounded by a constant.

How do we know where languages begin and where they end? It is widely assumed that languages exist as discrete, distinct entities, an idea that forms the basis of mono- and multilingualism, as well as of source and target languages in translation theory. What created that clear-cut division between languages? I argue that our current conception of language was invented as part of the process of the creation of the nation-state. The idea of a language, and therefore of translation, was a product of nation-state formation that required the construction of boundaries to divide homogeneous territories, peoples, and their languages. The Stammbaum model of linguistic filiation emerged as part of the same politicized ideology of modernity. Against this, I consider the alternative model of language mixture, which conceptualizes language as a transformative process of interaction without boundaries and challenges ideas of a language and of translation.

There are several variations of fuzzy Turing machines in the literature, many of them require a t-norm in order to establish their accepted language. This paper generalize the concept of non-deterministic fuzzy Turing machine - NTFM, replacing the t-norm operator for several aggregation functions. We establish the languages accepted by these machines, called fuzzy recursively enumerable languages or simply LFRE and show, among other results, which classes of LFRE are closed under unions and intersections.

A (factor-)reference in a word is a special symbol that refers to another factor in the same word; a reference is dereferenced by substituting it with the referenced factor. We introduce and investigate the class ref-REG of all languages that can be obtained by taking a regular language R and then dereferencing all possible references in the words of R. We show that ref-REG coincides with the class of languages defined by regular expressions as they exist in modern programming languages like Perl, Python, Java, etc. (often called REGEX languages).

We study what languages can be constructed from a non-regular language L using Boolean operations and synchronous or non-synchronous rational transductions. If all rational transductions are allowed, one can construct the whole arithmetical hierarchy relative to L. In the case of synchronous rational transductions, we present non-regular languages that allow constructing languages arbitrarily high in the arithmetical hierarchy and we present non-regular languages that allow constructing only recursive languages. A consequence of the results is that aside from the regular languages, no full trio generated by a single language is closed under complementation. Another consequence is that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the definition of any language from the arithmetical hierarchy in the corresponding Kripke structure using multimodal logic.

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.

Context-sensitive languages are usually omitted in undergraduate textbooks on Theory of Computation or studied only from structural point of view in graduate textbooks with very few classical examples and no techniques of design of context-sensitive grammars and their corresponding linear bounded automata. Here we present a case of study showing that such omission and lack of examples and techniques can be fulfilled using standard techniques of formal languages. In particular it is stablished the descriptional and time complexity of an ambiguous context-sensitive grammar and a deterministic linear bounded automaton for the context-sensitive language L = { a^mb^nc^mn : m, n >= 1}

In this paper, we define Watson-Crick linear grammars extending Watson-Crick regular grammars Subramanian et al. (CCSEIT’12 proceedings of the second international conference on computer science, science, engineering and information technology 151–156, 2012, [9]) with linear rules, and study their generative power. We show that Watson-Crick linear grammars can generate some context-sensitive languages. Moreover, we establish that the family of Watson-Crick regular languages proper subset of the family of Watson-Crick linear languages but it is not comparable with the family of linear languages.

International audience; In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form $u⁎$, where $u$ is a word. We provide effective equational characterisations of these classes, i.e. one can decide using our descriptions whether a given regular language belongs or not to each of them.

Idempotency languages are generated from a single word by iterated application of rules of the form [Formula: see text] for natural numbers m and n. We investigate these languages over alphabets of only one or two letters. The conditions under which the underlying rewrite relations are confluent are fully characterized. Then for many combinations of the parameters m and n we answer the question, whether the corresponding idempotency languages are regular or not. What remains open are only the cases where [Formula: see text].

Bounded context-free languages have been investigated for nearly fifty years, yet they continue to generate interest as seen from recent studies. Here, we present a number of results about bounded context-free languages. First we give a new (simpler) proof that every context-free language L ? w 1 * w 2 * ? w n * can be accepted by a PDA with at most 2 n - 3 reversals. We also introduce new collections of bounded context-free languages and present some of their interesting properties. Some of the properties are counter-intuitive and may point to some deeper facts about bounded CFLs. We present some results about semilinear sets and also present a generalization of the well-known result that over a one-letter alphabet, the families of context-free and regular languages coincide.

Let [Formula: see text] be a finite alphabet and [Formula: see text] the set of all words over [Formula: see text]. A subword-free language (also known as a hypercode) is an independent subset of [Formula: see text] with respect to the embedding order (denoted by [Formula: see text]) on [Formula: see text]. In this paper we introduce three subsets of the partial order [Formula: see text], and study three subclasses of languages defined by these subsets. They are out subword-free languages, left subword-free languages and right subword-free languages. The properties of these languages are established for determining their combinatorial and algebraic structures. By equipping them with two binary operations, respectively, all these classes of languages form semilattice-ordered semigroups. It is shown that they are freely generated by [Formula: see text] in three subvarieties of semilattice-ordered semigroups, respectively. It is also shown that the word problems for these free algebras are solvable.

We investigate the descriptional and computational complexity of boundary sets of regular and context-free languages. For a letter a, the right (left, respectively) a-boundary set of a language L consists of the words in L whose a-predecessor or a-successor w.r.t. the prefix (suffix, respectively) relation is not in L. For regular languages described by deterministic finite automata (DFAs) we give tight bounds on the number of states for accepting boundary sets. Moreover, the question whether the boundary sets of a regular language is finite is shown to be NL -complete for DFAs, while it turns out to be PSPACE -complete for nondeterministic devices. Boundary sets for context-free languages are not necessarily context free anymore. Here we find a subtle difference of right and left a-boundary sets. While right a-boundary sets of deterministic context-free languages stay deterministic context free, we give an example of a deterministic context-free language whose a-boundary set is already non-context free. In fact, the finiteness problem for a-boundary sets of context-free languages becomes undecidable.

The characterization of the structure of palindromic regular and palindromiccontext-free languages is described by S. Horvath, J. Karhumaki,and J. Kleijn in 1987. In this paper alternative proofs are givenfor these characterizations.

Ehrenfeucht, Parikh and Rozenberg gave an interesting characterisation of the regular languages called the block pumping property. When requiring this property only with respect to members of the language but not with respect to nonmembers, one gets the notion of block pumpable languages. It is shown that these block pumpable are a more general concept than regular languages and that they are an interesting notion of their own: they are closed under intersection, union and homomorphism by transducers; they admit multiple pumping; they have either polynomial or exponential growth.

This article shows a general result about finite monoids and weight reducing string rewriting systems. As a consequence it proves a long standing conjecture in formal language theory: All regular languages are Church-Rosser congruential. The class of Church-Rosser congruential languages was introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential if there exists a finite, confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S . It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but the conjecture was that all regular languages are of this form. The article offers a stronger statement: A language is regular if and only if it is strongly Church-Rosser congruential. It is the journal version of the conference abstract which was presented at ICALP 2012.

Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all these numbers of states are optimal. After this, we completely characterize the class of languages recognized by 1-state GFAs, which is the only nontrivial class of languages recognized by 1-state automata. Finally, we consider the variations of PFAs, QFAs, and GFAs based on the notion of inclusive/exclusive cutpoint, and present some results on their expressive power.

Recently, researchers studied the state complexity of boundary — [Formula: see text] — of regular languages L motivated from the famous Kuratowski’s 14-theorem. Prefix codes — a set of languages — play an important role in several applications. We consider prefix-free regular languages and investigate the state complexity of two operations, [Formula: see text] and [Formula: see text] for prefix-free regular languages. Based on the unique structural properties of a prefix-free minimal DFA, we compute the precise state complexity of [Formula: see text] and [Formula: see text]. We then present the tight bound over a quaternary alphabet for [Formula: see text] and [Formula: see text]. Our results are smaller than the composition of the state complexity function for individual operations of prefix-free regular languages.

In the late nineteen sixties it was observed that the r.e. languages form an infinite proper hierarchy [Formula: see text] based on the size of the Turing machines that accept them. We examine the fundamental position of the finite languages and their complements in the hierarchy. We show that for every finite language L one has that L, [Formula: see text] for some [Formula: see text] where m is the length of the longest word in L, c is the cardinality of L, and [Formula: see text]. If [Formula: see text], then [Formula: see text] for some [Formula: see text]. We also prove that for every n, there is a finite language Ln with [Formula: see text] such that [Formula: see text] but Ln, [Formula: see text] for some [Formula: see text]. Several further results are shown that how the hierarchy can be separated by increasing chains of finite languages. The proofs make use of several auxiliary results for Turing machines with advice.

In this paper we look at words for bodies of water (e.g., words for ‘lake’ and ‘river’) in a large number of a posteriori and mixed artificial languages. After presenting the data and briefly discussing some of them, we analyze some aspects of them, including which meanings seem to be more basic than others. For example, words meaning ‘river’ appear to be unmarked with respect to words meaning similar, but smaller, bodies of water (e.g., ‘brook’), since some artificial languages derive the latter from the former, but no languages in our sample derive the latter from the former. This sort of analysis can be applied to other semantic fields in artificial languages.

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$$w=uxv to be the set of all strings $$v^Rxu^R$$vRxuR, where $$uv \ne \lambda $$uv?? 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.

Recently, Dassow et al. connected partial words and regular languages. Partial words are sequences in which some positions may be undefined, represented with a "hole" symbol ?. If we restrict what the symbol ? can represent, we can use partial words to compress the representation of regular languages. Doing so allows the creation of so-called ?-DFAs, smaller than the DFAs recognizing the original language L, which recognize the compressed language. However, the ?-DFAs may be larger than the NFAs recognizing L. In this paper, we investigate a question of Dassow et al. as to how these sizes are related.

The ordered restarting automaton (processing strings) is introduced, and it is shown that its nondeterministic variant is very expressive, as it accepts some languages that are not even context-free, while the deterministic ordered restarting automata just accept the regular languages. Then three different extensions of the deterministic ordered restarting automaton to two-dimensional inputs are defined that differ in the way in which they can move their read/write windows. We compare the classes of picture languages that these types of automata accept to each other and to some well studied classes of picture languages from the literature, and we present some closure and non-closure properties for them.

International audience; We study highly expressive query languages for unordered data trees, using as formal vehicles Active XML and extensions of languages in the while family. All languages may be seen as adding some form of control on top of a set of basic pattern queries. The results highlight the impact and interplay of different factors: the expressive power of basic queries, the embedding of computation into data (as in Active XML), and the use of deterministic vs. nondeterministic control. All languages are Turing complete, but not necessarily query complete in the sense of Chandra and Harel. Indeed, we show that some combinations of features yield serious limitations, analogous to FO-k definability in the relational context. On the other hand, the limitations come with benefits such as the existence of powerful normal forms providing opportunities for optimization. Other languages are ``almost'' complete, but fall short because of subtle limitations reminiscent of the copy elimination problem in object databases.

The main goal in this paper is to use a dual equivalence in automata theory started in [25] and developed in [3] to prove a general version of the Eilenberg-type theorem presented in [4]. Our principal results confirm the existence of a bijective correspondence between three concepts; formations of monoids, formations of languages and formations of congruences. The result does not require finiteness on monoids, nor regularity on languages nor finite index conditions on congruences. We relate our work to other results in the field and we include applications to non-r-disjunctive languages, Reiterman s equational description of pseudovarieties and varieties of monoids., The authors gratefully acknowledge various discussions with Jean-Eric Pin. This work has been supported by the grants MTM2010-19938-C03-01 from the Ministerio de Ciencia e Innovacion (Spanish Government) and MTM2014-54707-C3-1-P from the Ministerio de Economia y Competitividad (Spanish Government) and FEDER (European Union). The first author has been supported by the grant No. 11271085 from the National Natural Science Foundation of China. The second author has been supported by the predoctoral grant AP2010-2764 from the Ministeriode Educacion (Spanish Government) and by an internship from CWI.

Operator precedence languages were introduced half a century ago by Robert Floyd to support deterministic and efficient parsing of context-free languages. Recently, we renewed our interest in this class of languages thanks to a few distinguishing properties that make them attractive for exploiting various modern technologies. Precisely, their local parsability enables parallel and incremental parsing, whereas their closure properties make them amenable to automatic verification techniques, including model checking. In this paper we provide a fairly complete theory of this class of languages: we introduce a class of automata with the same recognizing power as the generative power of their grammars; we provide a characterization of their sentences in terms of monadic second-order logic as has been done in previous literature for more restricted language classes such as regular, parenthesis, and input-driven ones; we investigate preserved and lost properties when extending the language sentences from finite ...

This chapter recognises the need for a lingua franca in scientific research, in order to enable collaborative working and the circulation of knowledge. However, it challenges the monolingual assumptions that the acceptance of such a lingua franca often implies. The contemporary cultural dominance of English as a lingua franca often eclipses any awareness of the diversity of languages on which the development of science has historically depended. It disguises the ways in which the development of knowledge depends on complex processes of translation—of concepts, terms and ideas—which reveal the inherently multilingual nature of scientific research. The chapter considers the interdependency of science and languages, underlining the extent to which scientific research as a fundamentally human endeavour relies on, and is enhanced by, a recognition of linguistic diversity.