Search

Most modern regular expression matching libraries (one of the rare exceptions being Google's RE2) allow backreferences, operations which bind a substring to a variable, allowing it to be matched again verbatim. However, both real-world implementations and definitions in the literature use different syntactic restrictions and have differences in the semantics of the matching of backreferences. Our aim is to compare these various flavors by considering the classes of formal languages that each can describe, establishing, as a result, a hierarchy of language classes. Beyond the hierarchy itself, some complexity results are given, and as part of the effort on comparing language classes new pumping lemmas are established, old classes are extended to new ones, and several incidental results on the nature of these language classes are given. [ABSTRACT FROM AUTHOR]

We study a sound verification method for parametric component-based systems. The method uses a resource logic, a new formal specification language for distributed systems consisting of a finite yet unbounded number of components. The logic allows the description of architecture configurations coordinating instances of a finite number of types of components, by means of inductive definitions similar to the ones used to describe algebraic data types or recursive data structures. For parametric systems specified in this logic, we show that decision problems such as reaching deadlock or violating critical section are undecidable, in general. Despite this negative result, we provide for these decision problems practical semi-algorithms relying on the automatic synthesis of structural invariants allowing the proof of general safety properties. The invariants are defined using the WS κ S fragment of the monadic second order logic, known to be decidable by a classical automata-logic connection, thus reducing a verification problem to checking satisfiability of a WS κ S formula. • We introduce a logic-based language for describing sets of configurations of parameterized distributed systems. • The language uses predicate symbols to hierarchically decompose the system architecture into specific patterns. • We address a parametric safety problem i.e., checking that reachable configurations stay clear of error configurations. • We show that deadlock freedom and critical section violation problems are undecidable, even for simple architectures. • We develop a verification method that synthesizes parametric invariants described using a decidable fragment of MSO. [ABSTRACT FROM AUTHOR]

We present, in outline, a constructive development of set theory in the style of A.P. Morse's classical counterpart [10]. Since the development is carried in a very precise formal language, it readily lends itself to computer-assisted proof-checking and program extraction from proofs. • A development of constructive set theory in Morse's formal language, which should facilitate both proof checking and program extraction from proofs. • A powerful, general induction theorem. • Discussion of aspects of the proof that the Continuum Hypothesis implies excluded middle. [ABSTRACT FROM AUTHOR]

This paper analyzes a new distinguishability operation for finite deterministic machines and languages. The research was inspired by the "Gedanken experiments" on sequential machines performed by Moore in 1956, and extends the study of the unary distinguishability operation to a binary one. Besides studying the new operation's properties, we give a tight bound of its state complexity on regular languages, including the case for finite languages. • We introduce a new binary operation on languages and finite state machines. • We compute the state complexity of this operation for deterministic machines. • The case of incomplete machines and finite languages is also studied. • We prove several properties of the set of minimal distinguishable words. • We improve the results by Moore, and by Shallit for minimal distinguishable words. [ABSTRACT FROM AUTHOR]

The circular splicing operation is a language-theoretic operation introduced by Head to model biological phenomena on circular DNA and RNAs. It acts on pairs of circular words under conditions defined by a set of rules. A circular splicing system S is defined by giving an initial set of circular words and a set of rules. S represents a circular language from a generative point of view (splicing language). There are open questions related to the computational power of these systems. For instance, a characterization of circular splicing systems generating regular circular languages is still lacking as well as a characterization of the structure of the regular splicing languages. In this paper we give results about these questions for a special class of hybrid systems named generalized marked systems. [ABSTRACT FROM AUTHOR]

The model of deterministic input-driven multi-counter automata is introduced and studied. On such devices, the input letters uniquely determine the operations on the underlying data structure that is consisting of multiple counters. We study the computational power of the resulting language families and compare them with known language families inside the Chomsky hierarchy. In addition, it is possible to prove a proper counter hierarchy depending on the alphabet size. This means that any input alphabet induces an upper bound which depends on the alphabet size only, such that k + 1 counters are more powerful than k counters as long as k is less than this bound. The hierarchy interestingly collapses at the level of the bound. Furthermore, we investigate the closure properties of the language families. For input-driven multi-counter automata with 0 or 1 counter, we discuss the computational complexity of their decidable problems. For k ≥ 2 counters, the decidability problems of emptiness, finiteness, universality, inclusion, equivalence, regularity, and context-freeness are shown to be non-semidecidable. Finally, we study descriptional complexity aspects of input-driven multi-counter automata. It is shown that a nondeterministic device can be determinized and that 2 n − 1 is a necessary and sufficient blow-up in the number of states for the determinization. For the operational state complexity of deterministic input-driven multi-counter automata under Boolean operations, tight bounds on the number of states are established. Finally, it turns out that the size trade-offs between deterministic input-driven multi-counter automata with k + 1 and k counters are non-recursive, that is, they are not bounded by any recursive function. [ABSTRACT FROM AUTHOR]

We are interested in regular expressions that represent word relations in an alphabet-invariant way—for example, the set of all word pairs (u , v) where v is a prefix of u independently of what the alphabet is. Current software systems of formal language objects do not have a mechanism to define such objects. Labelled graphs (transducers and automata) with alphabet-invariant and user-defined labels were considered in a recent paper. In this paper we study derivatives of regular expressions over labels (atomic objects) in some set B. These labels can be any strings as long as the strings represent subsets of a certain monoid. We show that the number of partial derivatives of any type B regular expression is linearly bounded, and that one can define partial derivative labelled graphs, whose transition labels can be elements of another label set X as long as X and B refer to the same monoid. We also show how to use derivatives directly to decide whether a given word is in the language of a regular expression over set specs. Set specs and pairing specs are label sets allowing one to express languages and relations over large alphabets in a natural and concise way such that many algorithms work directly on these labels without the need to expand these labels to linear or quadratic size expressions. [ABSTRACT FROM AUTHOR]

Context-free grammars are not able to capture cross-serial dependencies occurring in some natural languages. To overcome this issue, Seki et al. introduced a generalization called m -multiple context-free grammars (m -MCFGs), which deal with m -tuples of strings. We show that m -MCFGs are capable of comparing the number of consecutive occurrences of at most 2 m different letters. In particular, the language { a 1 n 1 a 2 n 2 ⋯ a 2 m + 1 n 2 m + 1 | n 1 ≥ n 2 ≥ ... ≥ n 2 m + 1 ≥ 0 } is (m + 1) -multiple context-free, but not m -multiple context-free. [ABSTRACT FROM AUTHOR]

We present a weight measure on formal languages based on the summands of a geometric series discounted by the fraction of words of certain length in the language, guaranteeing the weight to be a real value between 0 and 1 for any language. We show that this weight measure is computable for regular languages. As an application, we derive a distance metric between languages as the weight of their symmetric difference and show how it can be used in automatic grading of standard exercises in formal language theory classes. [ABSTRACT FROM AUTHOR]

• The topological entropy function is surjective. • Languages of deterministic epsilon-free k-counter automata have 0 entropy. • Languages of deterministic epsilon-free k-stack automata have bounded entropy. We introduce the notions of topological entropy of a formal language and of a topological automaton. We show that the entropy function is surjective and bound the entropy of languages accepted by deterministic ε -free push-down automata with an arbitrary amount of stacks. [ABSTRACT FROM AUTHOR]

Constraint LTL over clocks (CLTLoc) is an extension of LTL allowing for atomic formulae of the form x < c or x = c , which constrain the time delay measured by clock x with respect to constant value c. In a previous work, we showed that CLTLoc is equivalent to Timed Automata. The result was proven by considering a clock semantics that conforms to the original definition by Alur and Dill, i.e., when clocks are reset (i.e., equal to 0) in the origin, both CLTLoc and Timed Automata define the class of Timed ω -Regular languages. In this paper, we show that if we allow the clocks to have any value in the origin, the power of the formalism to express timed languages does not change, as long as non-Zeno languages are considered. If Zeno languages are allowed, then CLTLoc is strictly more powerful than TA. As a consequence of these results, we also show that non-Zeno Timed ω -Regular languages are closed with respect to the left quotient operation with timed regular languages over finite words. [ABSTRACT FROM AUTHOR]

We consider several language-theoretic aspects of various notions of unique decipherability (or unique factorization) in formal languages. Given a language L at some position within the Chomsky hierarchy, we investigate the language of words UD (L) in L ⁎ that have unique factorization over L. We also consider similar notions for weaker forms of unique decipherability, such as numerically decipherable words ND (L) , multiset decipherable words MSD (L) and set decipherable words SD (L). Although these notions of unique factorization have been considered before, it appears that the languages of words having these properties have not been positioned in the Chomsky hierarchy up until now. We show that UD (L) , ND (L) , MSD (L) and SD (L) need not be context-free if L is context-free. In fact ND (L) and MSD (L) need not be context-free even if L is finite, although UD (L) and SD (L) are regular in this case. We show that if L is context-sensitive, then so are UD (L) , ND (L) , MSD (L) and SD (L). We also prove that the membership problem (resp., emptiness problem) for these classes is PSPACE-complete (resp., undecidable). We finally determine upper and lower bounds on the length of the shortest word of L ⁎ not having the various forms of unique decipherability into elements of L. [ABSTRACT FROM AUTHOR]

The paper determines the number of states in finite automata necessary to represent "unambiguous" variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m -state and an n -state deterministic finite automata (DFA), the state complexity is m n − 1 ; for the unambiguous concatenation, it is known to be m 2 n − 1 − 2 n − 2 (Daley et al., "Orthogonal concatenation: language equations and state complexity" , J. UCS , 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be 3 8 2 n + 1. In the case of a unary alphabet, disjoint union requires up to 1 2 m n states in a DFA, unambiguous concatenation has state complexity m + n − 2 , and unambiguous star requires n − 2 states in the worst case. For nondeterministic finite automata, as well as for unambiguous finite automata, the complexity for disjoint union is m + n , for unambiguous concatenation, square, and star, the resulting complexities are m + n , 2 n , and n + 1 , respectively, and all of them are witnessed by binary languages. In the unary nondeterministic or unambiguous case, the corresponding complexities are m + n for disjoint union, m + n − 1 and 2 n − 1 for unambiguous concatenation and square, respectively, and n − 1 for unambiguous star. [ABSTRACT FROM AUTHOR]

Epigenomics is the study of modifications on the genetic material of a cell that do not depend on changes in the DNA sequence, since those latter involve specific proteins around which DNA wraps. The end result is that Epigenomic changes have a fundamental role in the proper working of each cell in Eukaryotic organisms. A particularly important part of Epigenomics concentrates on the study of chromatin, that is, a fiber composed of a DNA-protein complex and very characterizing of Eukaryotes. Understanding how chromatin is assembled and how it changes is fundamental for Biology. In more than thirty years of research in this area, Mathematics and Theoretical Computer Science have gained a prominent role, in terms of modeling and mining, regarding in particular the so-called 10 nm fiber. Starting from some very basic notions of Biology, we briefly illustrate the recent advances obtained via laboratory experiments on the organization and dynamics of chromatin. Then, we mainly concentrate our attention on the contributions given by Combinatorial and Informational Methodologies, that are at the hearth of Theoretical Computer Science, to the understanding of mechanisms determining the 10 nm fiber. We conclude highlighting several directions of investigation that are perceived as important and where Theoretical Computer Science can provide high impact results. [ABSTRACT FROM AUTHOR]

We define a notion of randomness for individual and collections of formal languages based on automatic martingales acting on sequences of words from some underlying domain. An automatic martingale bets if the incoming word belongs to the target language or not. Then randomness of both single languages and collections of languages is defined as a failure of automatic martingale to gain an unbounded capital by betting on the target language according to an incoming sequence of words, or a text. The randomness of formal languages turned out to be heavily dependent on the text. For very general classes of texts, any nonregular language happens to be random when considered individually. As for collections of languages, very general classes of texts permits nonrandomness of automatic families of languages only. On the other hand, an arbitrary computable language is shown to be nonrandom under certain dynamic texts. [ABSTRACT FROM AUTHOR]

Edit distance ℓ -neighbourhood of a formal language is the set of all strings that can be transformed to one of the strings in this language by at most ℓ insertions and deletions. Both the regular and the context-free languages are known to be closed under this operation, whereas the family recognized by deterministic pushdown automata is not. This paper establishes the closure of the family recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the edit distance neighbourhood operation. For an n -state nondeterministic IDPDA with n stack symbols, an automaton for its edit distance ℓ -neighbourhood using O (n ℓ + 1) states is constructed, and an asymptotically matching lower bound is established. For an n -state deterministic IDPDA, its 1-neighbourhood in the worst case requires a deterministic IDPDA with at least 2 Ω (n 2) states. [ABSTRACT FROM AUTHOR]

A picture, or two-dimensional (2D) string, is a rectangular array of symbols over a finite alphabet. In this paper, we introduce the notion of fullness for sets of strings and sets of pictures. Fullness is a local counterpart of completeness. While in 1D fullness coincides with completeness, in 2D complete sets of pictures are a subset of full ones. This new notion allows introducing the encoding of a picture. The definition of encoding is based on the one of cutting decomposition. If a set of pictures X is full then any picture has an encoding over X ; furthermore, the encoding is unique if X is a univocally full set. Univocally full sets coincide with the maximal strong prefix codes of pictures that were recently introduced. At last, we show an encoding algorithm for pictures, which relies on a new tree data structure to represent univocally full sets. [ABSTRACT FROM AUTHOR]

For a closure operation c and an involution i defined on a language family L , we define N c , i L (L) as the number of languages which can be obtained from L by repeated applications of c and i. The orbit O L (c , i) of c and i is defined as the set of all these numbers. We determine the orbit for some classical language theoretic closure operators and the involution complement. We show that complement and reversal behave very different with respect to some special closure operators. Moreover, we prove that, for an arbitrary closure operator and reversal, some "small" numbers cannot be avoided in the orbit. [ABSTRACT FROM AUTHOR]

Abstract Let G be a group and let φ : Σ ⁎ → G be a monoid homomorphism from the set of all strings Σ ⁎ over some finite alphabet Σ onto the group G. The set Σ is then called a generating set for G and the language { 1 } φ − 1 ⊆ Σ ⁎ is called the word problem of G with respect to the generating set Σ (via the homomorphism φ) and is denoted by W (G , Σ). We consider nine conditions that hold in each such language of the form W (G , Σ) and determine which combinations of these conditions are equivalent to the property of the language in question being the word problem of a group. We show that each of these nine conditions is decidable for the family of regular languages but that each is undecidable for the family of one-counter languages (the languages accepted by one-counter pushdown automata). We also show that the property of a language being the word problem of a group is undecidable for the family of one-counter languages but is decidable for the family of deterministic context-free languages (the languages accepted by deterministic pushdown automata). [ABSTRACT FROM AUTHOR]

Abstract It is well known that the “store language” of every pushdown automaton — the set of store configurations (state and stack contents) that can appear as an intermediate step in accepting computations — is a regular language. Here many models of language acceptors with various store structures are examined, along with a study of their store languages. For each model, an attempt is made to find the simplest model that accepts their store languages. Some connections between store languages of one-way and two-way machines are demonstrated, as with connections between nondeterministic and deterministic machines. A nice application of these store language results is also presented, showing a general technique for proving families accepted by many deterministic models are closed under right quotient with regular languages, resolving some open questions (and significantly simplifying proofs for others that are known) in the literature. Lower bounds on the space complexity of Turing machines for having non-regular store languages are obtained. [ABSTRACT FROM AUTHOR]

We study the local limit distribution of the number of occurrences of a symbol in words of length n generated at random in a regular language according to a rational stochastic model. We present an analysis of the main local limits when the finite state automaton defining the stochastic model consists of two primitive components. The limit distributions depend on several parameters and conditions, such as the main constants of mean value and variance of our statistics associated with the two components, and the existence of communications from the first to the second component. The convergence rate of these results is always of order O (n − 1 / 2). For the same statistics we also prove an analogous O (n − 1 / 2) convergence rate of the Gaussian local limit law whenever the stochastic model consists of one primitive component. [ABSTRACT FROM AUTHOR]

Let α , β be real numbers and b ≥ 2 be an integer. Allouche and Shallit showed that the sequence { ⌊ α n + β ⌋ } n ≥ 0 is b -regular if and only if α is rational. In this paper, using a base-independent regular language, we prove a similar result that the sequence { ⌊ log b ⁡ ( α n + β ) ⌋ } n ≥ 0 is b -regular if and only if α is rational, where α > 0 , β ≥ 0 . In particular, when α = 2 , β = 0 and b = 2 , we answer a question of Allouche and Shallit that the sequence { ⌊ 1 2 + log 2 ⁡ n ⌋ } n ≥ 1 is not 2-regular, which has previously been proved by Bell, Moshe and Rowland respectively. [ABSTRACT FROM AUTHOR]

A pseudoknot is a crucial intra-molecular structure formed primarily in RNA strands and closely related to important biological processes. This motivates us to define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation. We design an efficient algorithm that decides whether or not a given string is a pseudoknot of a regular language L . Our algorithm runs in linear time if L is given by a deterministic finite automaton. We study closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms that check whether or not a regular language L contains a pseudoknot or a pseudoknot generated by some string of L . Furthermore, we show that the corresponding questions for context-free languages are undecidable. [ABSTRACT FROM AUTHOR]

In 1973, Greibach ("The hardest context-free language", SIAM J. Comp. , 1973) constructed a context-free language L 0 with the property that every context-free language can be reduced to L 0 by a homomorphism, thus representing it as an inverse homomorphic image h − 1 (L 0). In this paper, a similar characterization is established for a family of grammars equipped with operators for referring to the left context of any substring, recently defined by Barash and Okhotin ("An extension of context-free grammars with one-sided context specifications", Inform. Comput. , 2014). An essential step of the argument is a new normal form for grammars with context operators, in which every nonterminal symbol defines only strings of odd length in left contexts of even length: the even-odd normal form. The characterization is completed by showing that the language family defined by grammars with context operators is closed under inverse homomorphisms; actually, it is closed under injective nondeterministic finite transductions. [ABSTRACT FROM AUTHOR]

JSON Schema is an evolving standard for describing families of JSON documents. It is a logical language, based on a set of assertions that describe features of the JSON value under analysis and on logical or structural combinators for these assertions, including a negation operator. Most logical languages with negation enjoy negation closure : for every operator, they have a negation-dual that allows negation to be pushed through the operator. We show that this is not the case for JSON Schema, study how that changed with the latest versions of the Draft, and discuss how the language may be enriched accordingly. To this aim, we exploit an algebraic reformulation of JSON Schema, which is helpful for the formal manipulation of the language. [ABSTRACT FROM AUTHOR]

In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w , the tape contents is reduced to a particular word within a finite number of applications of these contextual rewritings. Here we extend the limited context restarting automata by using additional global means to structure the reductions they execute. In fact, we study regulated lc-R-automata, for which a regular control language is used to restrict the set of admissible reduction sequences, and we propose random context conditions to restrict the place at which a transition of an lc-R-automaton can be applied. [ABSTRACT FROM AUTHOR]

We consider a new type of transducer that does not scan sequentially the input word. This transducer is actually a network of polarized evolutionary processors ( NPEP ) which receives a word as input and collects in the output node, when the computation halts, the translation of the input word. We prove that these transducers can simulate the work of generalized sequential machines on every input. Furthermore, all words obtained by a given finite state transducer by the shortest computations on a given word can also be computed by the new transducers. Unlike the case of generalized sequential machines, every recursively enumerable language can be the transduction, defined by the new transducer, of a very simple regular language. [ABSTRACT FROM AUTHOR]

We consider d -dimensional contextual array grammars and investigate their computational power when using various control mechanisms – matrices, regular control languages, and tissue P systems, which work like regular control languages, but may end up with a final check for the non-applicability of some rules. For d ≥ 2 , d -dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. The use of tissue P systems with their final non-applicability check even yields some additional computational power. In the 1-dimensional case, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages can be characterized as the family of array images of the linear languages, which for a one-letter alphabet means that it coincides with the family of regular 1-dimensional array languages. [ABSTRACT FROM AUTHOR]

Grammars with valuations are context-free rewriting mechanisms where the derivation process is controlled by a recursive function that evaluates strings. They have been introduced by Jürgen Dassow as models for the molecular replication process taking into account its selective character. A symbol is active in a grammar with valuation if it can be rewritten non-identically. This paper studies the effect of restricting the number of active symbols in grammars with valuations and several variants thereof to their generative power. It is investigated in which cases the number of active symbols induces infinite strict hierarchies and when the hierarchies collapse. The induced language families are compared among one another. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this work we introduce the operation of prefix–suffix square reduction as the inverse of the prefix–suffix duplication studied in the literature. This operation reduces all possible squares that are prefixes or suffixes of a word to one half of these squares. Two variants are considered, depending on the unbounded and bounded length of the removed prefix or suffix. We investigate the complexity of the (non-uniform) membership problem for the prefix–suffix square reduction of a given language and the closure properties of some classes of languages under these operations as well as under their iterated variants. Afterwards, we define the primitive prefix–suffix square root of a word w as a word x that can be obtained from w by iterated prefix–suffix square reductions and it is irreducible in turn, i.e., no further prefix or suffix square reduction can be applied. We prove that the language of primitive prefix–suffix square roots of all words over an alphabet is never regular for alphabets with at least two symbols in the unbounded case, and always regular in the bounded case. The paper ends with a brief discussion on some open problems and some algorithmic aspects. [ABSTRACT FROM AUTHOR]

We extend to spiking neural P systems a notion investigated in the “standard” membrane systems: the language of the traces of a distinguished object. In our case, we distinguish a spike by “marking” it and we follow its path through the neurons of the system, thus obtaining a language. Several examples are discussed and some preliminary results about this way of associating a language with a spiking neural P system are given, together with a series of topics for further research. For instance, we show that each regular language is the morphic image of a trace language intersected with a very particular regular language, while each recursively enumerable language over the one-letter alphabet is the projection of a trace language. In all proofs we try to keep the size of used systems (number of neurons, of rules in each neuron, of spikes consumed or removed by rules) as small as possible. [ABSTRACT FROM AUTHOR]

The set of all strings Parikh equivalent to a string in a language L is called the permutation of L . The permutation of a finite n -state DFA (deterministic finite automaton) language over a binary alphabet can be recognized by a DFA with n 2 − n + 2 2 states. We show that if the language consists of equal length binary strings the bound can be improved to f ( n ) = n 2 + n + 1 3 and for every n congruent to 1 modulo 3 there exists an n -state DFA A recognizing a set of equal length strings such that the minimal DFA for the permutation of L ( A ) needs f ( n ) states. [ABSTRACT FROM AUTHOR]

A regular language is k -piecewise testable ( k -PT) if it is a Boolean combination of languages of the form L a 1 a 2 … a n = Σ ⁎ a 1 Σ ⁎ a 2 Σ ⁎ ⋯ Σ ⁎ a n Σ ⁎ , where a i ∈ Σ and 0 ≤ n ≤ k . Given a finite automaton A , if the language L ( A ) is piecewise testable, we want to express it as a Boolean combination of languages of the above form. The idea is as follows. If the language is k -PT, then there exists a congruence ∼ k of finite index such that L ( A ) is a finite union of ∼ k -classes. Every such class is characterized by an intersection of languages of the from L u , for | u | ≤ k , and their complements. To represent the ∼ k -classes, we make use of the ∼ k -canonical DFA. We identify the states of the ∼ k -canonical DFA whose union forms the language L ( A ) and use them to construct the required Boolean combination. We study the computational and descriptional complexity of related problems. [ABSTRACT FROM AUTHOR]

We establish the relation between two language recognition models that use counters and operate in real-time: Greibach's partially blind machines operating in real time (RT-PBLIND), which recognize Petri Net languages, and the consensually regular (CREG) language model of the authors. The latter is based on synchronized computational threads of a finite automaton, where at each step one thread acts as the leader and all other threads as followers. We introduce two new normal forms of RT-PBLIND machines (and Petri Nets), such that counter operations are scheduled and rarefied, and transitions are quasi-deterministic, i.e., the finite automaton obtained by eliminating counter moves is deterministic. We prove that the CREG family can simulate any normalized RT-PBLIND machine, but it also contains the non-RT-PBLIND language { a n b n | n > 1 } ⁎ . [ABSTRACT FROM AUTHOR]

A bidimensional bifix (in short bibifix ) of a square matrix T is a square submatrix of T which occurs in the top-left and bottom-right corners of T . This allows us to extend the definition of bifix-free words and cross-bifix-free set of words to bidimensional structures. In this paper we exhaustively generate all the bibifix -free square matrices and we construct a particular non-expandable cross-bibifix -free set of square matrices. Moreover, we provide a Gray code for listing this set. [ABSTRACT FROM AUTHOR]

Visibly Pushdown Automata ( VPA ) are a special case of pushdown machines where the stack operations are driven by the input. In this paper, we consider VPA with multiple stacks , namely n-VPA , with n > 1 . These automata introduce a useful model to effectively describe concurrent pushdown systems using a simple communication mechanism between stacks. We show that n -VPA are strictly more expressive than VPA. Indeed, n -VPA accept some context-sensitive languages that are not context-free and some context-free languages that are not accepted by any VPA. Nevertheless, we show that the class of languages accepted by n -VPA is closed under union and intersection. On the contrary, this class turns out to be neither closed under complementation nor determinizable. Moreover, we show that the emptiness problem for n -VPA is undecidable. By adding an ordering constraint on stacks ( n -OVPA), decidability of emptiness can be recovered, as well as the closure under complementation. Using these properties along with the automata-theoretic approach, one can prove that the model checking problem over n -OVPA models against n -OVPA specifications is decidable. [ABSTRACT FROM AUTHOR]

We provide an algorithm for learning an unknown regular set of infinite words using membership and equivalence queries. Three variations of the algorithm learn three different canonical representations of regular omega languages using the notion of families of dfa s. One is of size similar to L $ , a dfa representation recently learned using L ⁎ by Farzan et al. The second is based on the syntactic forc , introduced by Maler and Staiger. The third is introduced herein. We show that the second and third can be exponentially smaller than the first, and the third is at most as large as the second, with up to a quadratic saving with respect to the second. [ABSTRACT FROM AUTHOR]

We introduce and explore a model for parallel learning of families of languages computable by finite automata. In this model, an algorithmic or automatic learner takes on n different input languages and identifies at least m of them correctly. For finite parallel learning, for large enough families, we establish a full characterization of learnability in terms of characteristic samples of languages. Based on this characterization, we show that it is the difference n − m , the number of languages which are potentially not identified, which is crucial. Similar results are obtained also for parallel learning in the limit. We consider also parallel finite learnability by finite automata and obtain some partial results. A number of problems for automatic variant of parallel learning remain open. [ABSTRACT FROM AUTHOR]

This paper provides efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: • The classes of the Boolean hierarchy over level Σ 1 of the dot-depth hierarchy are decidable in NL (previously only the decidability was known). The same remains true if predicates mod d for fixed d are allowed. • If modular predicates for arbitrary d are allowed, then the classes of the Boolean hierarchy over level Σ 1 are decidable. • For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level Σ 2 of the Straubing–Thérien hierarchy are decidable in NL. This is the first decidability result for this hierarchy. • The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for NL. • The membership problems for quasi-aperiodic languages and for d -quasi-aperiodic languages are logspace many-one complete for PSPACE. [ABSTRACT FROM AUTHOR]

Although a lot of research has been done on the factor complexity (also called subword complexity) of morphic words obtained as fixed points of iterated morphisms, there has been little development in exploring algorithms that can efficiently compute their abelian complexity. The factor complexity counts the number of factors of a given length n , while the abelian complexity counts that number up to letter permutation. We propose and analyze a simple O ( n ) algorithm for quickly computing the exact abelian complexities for all indices from 1 up to n , when considering binary uniform morphisms. Using our algorithm we also analyze the structure in the abelian complexity for that class of morphisms. Our main result implies, in particular, that the infinite word over the alphabet { − 1 , 0 , 1 } constructed from the consecutive forward differences of the abelian complexity of a fixed point of a binary uniform morphism is in fact an automatic sequence with the same morphic length. Since the proof produces morphisms that typically contain many redundant letters, we present an efficient algorithm to eliminate them in order to simplify the morphisms and to see the patterns produced more clearly. [ABSTRACT FROM AUTHOR]

We investigate a subclass of well-structured transition systems (WSTS), the trace bounded —in the sense of Ginsburg and Spanier (1964), [1] —complete deterministic ones, which we claim provide an adequate basis for the study of forward analyses as developed by Finkel and Goubault-Larrecq (2012), [2] . Indeed, we prove that, unlike other conditions considered previously for the termination of forward analysis, trace boundedness is decidable. Trace boundedness turns out to be a valuable restriction for WSTS verification, as we show that it further allows to decide all ω -regular properties on the set of infinite traces of the system. [ABSTRACT FROM AUTHOR]

The paper proposes a temporal extension of Recursive State Machines (RSMs), called Timed RSMs (TRSMs), which consists of an indexed collection of Timed Automata, called components. Each component can invoke other components in a potentially recursive manner. Besides being able to model procedure calls and recursion, TRSMs are equipped with the ability to suspend the evolution of time within a component when another component is invoked and to recover it when control is given back at return time. This mechanism is realized by storing clock valuations into an implicit stack at invocation time and restoring them upon return. Indeed, TRSMs can be related to an extension of Pushdown Timed Automata, called EPTAs, where an additional stack, coupled with the standard control stack, is used to store temporal valuations of clocks. The expressiveness and computational properties of the resulting model are analyzed, showing that it can be used to recognize timed languages exhibiting context-free properties not only in the untimed “control” part, but also in the associated temporal dimension. The reachability problem for both TRSMs and EPTAs is investigated, showing that the problem is undecidable in the general case. However, the problem becomes decidable for two meaningful subclasses, called I-TRSM and L-TRSM , obtained by suitably constraining the set of clocks to reset at invocation time and to restore at return time. The considered subclasses are compared with the corresponding EPTA s subclasses through bisimulation of their timed LTSs. The complexity of the reachability problem for L-TRSM and I-TRSM is proved to be EXPTIME -complete and PSPACE -complete, respectively. Moreover, we prove that such classes strictly enhance the expressive power of Timed Automata and of Pushdown Timed Automata, forming a proper hierarchy. [ABSTRACT FROM AUTHOR]

Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (A. Okhotin, “On the equivalence of linear conjunctive grammars to trellis automata”, RAIRO ITA , 2004), and this family is known to be incomparable with the context-free languages (V. Terrier, “On real-time one-way cellular array”, Theoret. Comput. Sci. , 1995). This paper demonstrates the containment of the languages accepted by input-driven pushdown automata (a.k.a. visibly pushdown automata) in the family of linear conjunctive languages, which is established by a direct simulation of an input-driven automaton by a one-way real-time cellular automaton. On the other hand, it is shown that the language families defined by the unambiguous grammars, the LR ( k ) grammars and the LL ( k ) grammars are incomparable with the linear conjunctive languages. [ABSTRACT FROM AUTHOR]

We give a method for specifying ultrafilter equations and identify their projections on the set of profinite words. Let B be the set of languages captured by first-order sentences using unary predicates for each letter, arbitrary uniform unary numerical predicates and a predicate for the length of a word. We illustrate our methods by giving ultrafilter equations characterising B and then projecting these to obtain profinite equations characterising B ∩ Reg . This suffices to establish the decidability of the membership problem for B ∩ Reg . [ABSTRACT FROM AUTHOR]

One aspect of DNA Computing is the possibility of using DNA molecules for solving some “complicated” computational problems. In this context, the DNA code word design problem assumes a fundamental role: given a problem encoded in DNA strands and biochemical processes, the final computation is a concatenation of the input DNA strands that must allow us to recover the solution of the given problem in terms of the input (unique decipherability). Thus the initial set of DNA strands must be a code. In addition, it should satisfy some restrictions, called here DNA properties, in order to prevent them from interacting in undesirable ways. So a new interest towards the design of efficient algorithms for testing whether a language X is a code, has arisen from (wet) DNA Computing, but, as far as we know, only when X is a finite set. In this paper we provide an algorithm for testing whether an infinite but regular set of words is a code that avoids some DNA properties among unwanted intermolecular and intramolecular hybridizations. [ABSTRACT FROM AUTHOR]

For each regular language L we describe a family of canonical nondeterministic acceptors (nfas). Their construction follows a uniform recipe: build the minimal dfa for L in a locally finite variety V , and apply an equivalence between the category of finite V -algebras and a suitable category of finite structured sets and relations. By instantiating this to different varieties, we recover three well-studied canonical nfas: V = boolean algebras yields the átomaton of Brzozowski and Tamm, V = semilattices yields the jiromaton of Denis, Lemay and Terlutte, and V = Z 2 -vector spaces yields the minimal xor automaton of Vuillemin and Gama. Moreover, we obtain a new canonical nfa called the distromaton by taking V = distributive lattices. Each of these nfas is shown to be minimal relative to a suitable measure, and we derive sufficient conditions for their state-minimality. Our approach is coalgebraic, exhibiting additional structure and universal properties of the canonical nfas. [ABSTRACT FROM AUTHOR]

A deterministic L system generates an infinite word α if each word in its derivation sequence is a prefix of the next, yielding α as a limit. We generalize this notion to arbitrary L systems via the concept of prefix languages. A prefix language is a language L such that for all x , y ∈ L , x is a prefix of y or y is a prefix of x . Every infinite prefix language determines a single infinite word. Where C is a class of L systems (e.g. 0L, DT0L), we denote by ω ( C ) the class of infinite words determined by the prefix languages in C . This allows us to speak of infinite 0L words, infinite DT0L words, etc. We categorize the infinite words determined by a variety of L systems, showing that the whole hierarchy collapses to just three distinct classes of infinite words: ω ( PD0L ) , ω ( D0L ) , and ω ( CD0L ) . Our results are obtained with the help of a pumping lemma which we prove for T0L systems. [ABSTRACT FROM AUTHOR]

Given a string, a non-overlapping inversion is to reverse some non-overlapping fragments of the string simultaneously. We define a non-overlapping inversion operation to be the computation of all possible non-overlapping inversions. We apply the operation on a string, which gives rise to a set of strings, and construct an NFA recognizing the set. Then, we design an efficient DFA reduction algorithm from the resulting NFA. We also consider the non-overlapping inversion operation on a language and show the closure properties for regular, context-free and context-sensitive languages. We furthermore examine iterative non-overlapping inversions and establish the closure properties. Finally, we introduce non-overlapping inversion-free languages and present the decidability results for regular and context-free languages. [ABSTRACT FROM AUTHOR]

In a recent paper (M. Barash, A. Okhotin, “An extension of context-free grammars with one-sided context specifications”, Inform. and Comput. , 2014), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O ( n 4 ) , where n is the length of the input string. [ABSTRACT FROM AUTHOR]