Search

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]

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 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]

The paper introduces node replacement graph grammars with dynamic node relabeling as an extension of the eNCE families of graph grammars. Initiated by NLC grammars in which graph embedding is based on node labels only, node distinction of the embedded graph extended NLC grammars to NCE grammars and dynamic edge relabeling further extended NCE grammars to eNCE grammars. Now, dynamic node relabeling, the node counterpart of the dynamic edge relabeling, is introduced as the next extension, which we call neNCE. The paper analyzes basic language-theoretical properties of the neNCE system. [ABSTRACT FROM AUTHOR]

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

Abstract: Henkin quantifiers, when applied on Boolean formulae, yielding the so-called dependency quantified Boolean formulae (DQBFs), offer succinct descriptive power specifying variable dependencies. Despite their natural applications to games with incomplete information, logic synthesis with constrained input dependencies, etc., DQBFs remain a relatively unexplored subject however. This paper investigates their basic properties, including formula negation and complement, formula expansion, prenex and non-prenex form conversions, and resolution. In particular, the proposed DQBF formulation is established from a synthesis perspective concerned with Skolem-function models and Herbrand-function countermodels. Also a generalized resolution rule is shown to be sound, but incomplete, for DQBF evaluation. [Copyright &y& Elsevier]

Abstract: This paper deals with regulated grammars. Specifically, it studies one-sided random context grammars. It demonstrates that any recursively enumerable language can be generated by these grammars with no more than two right random context rules. [Copyright &y& Elsevier]

Abstract: Cassaigne conjectured in 1994 that any pattern with m distinct variables of length at least is avoidable over a binary alphabet, and any pattern with m distinct variables of length at least is avoidable over a ternary alphabet. Building upon the work of Rampersad and the power series techniques of Bell and Goh, we obtain both of these suggested strict bounds. Similar bounds are also obtained for pattern avoidance in partial words, sequences where some characters are unknown. [Copyright &y& Elsevier]

Abstract: Following recent works that connect two-variable logic to circuits and monoids, as well as recent techniques for obtaining algebraic and logical characterizations of threshold circuits, we present an algebraic and logical characterization of the language recognition power of uniform linear threshold circuits. More specifically, for numerical predicate sets satisfying a certain closure property, we characterize the class of languages recognized by -uniform linear threshold circuits as exactly those which are recognized by a particular class of two-variable formulas that use majority quantifiers and predicates, and are exactly those which can be recognized by a particular class of weakly blocked products of typed monoids. This correspondence will hold for any numerical predicate set which is -closed and whose predicates do not depend on the input length. [Copyright &y& Elsevier]

Abstract: In his 1966 book, “The Mathematical Theory of Context-Free Languages”, S. Ginsburg posed the following open problem: Find a decision procedure for determining if an arbitrary semilinear set is a finite union of stratified linear sets. It turns out that this problem (which remains open) is equivalent to the problem of synchronizability of multitape machines. Given an n-tape automaton M of a given type (e.g., nondeterministic pushdown automaton (NPDA), nondeterministic finite automaton (NFA), etc.) with a one-way read-only head per tape and a right end marker on each tape, we say that M is 0-synchronized (or aligned) if for every n-tuple that is accepted, there is an accepting computation on x such that at any time during the computation, all heads except those that have reached the end marker are on the same position (i.e., aligned). One of our main contributions is to show that Ginsburgʼs problem is equivalent to deciding for an arbitrary n-tape NFA M accepting (where and are distinct symbols) whether there exists an equivalent 0-synchronized n-tape NPDA . Ginsburgʼs problem is decidable if is required to be an NFA, and we will generalize this decidability over bounded inputs. It is known that if the inputs are unrestricted, the problem is undecidable. We also show several other related decidability and undecidability results. It may appear, as one of the referees suggested in an earlier version of this paper, that our main result can be written in first order logic. We explain why this is not the case in the Introduction. [Copyright &y& Elsevier]

Abstract: We use an information-theoretic notion, namely, (Shannon) information rate, to generalize common syntactic similarity metrics (like Hamming distance and longest common subsequences) between strings to ones between languages. We show that the similarity metrics between two regular languages are computable. We further study self-similarity of a regular language under various similarity metrics. As far as semantic similarity is concerned, we study the amplitude of an automaton, which intuitively characterizes how much a typical execution of the automaton fluctuates. Finally, we investigate, through experiments, how to measure similarity between two real-world programs using Lempel–Ziv compression on the runs at the assembly level. [Copyright &y& Elsevier]

Abstract: The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking to a propagating regular-controlled (context-free) grammar with appearance checking whose language has sentences of the form , where and is a parse of  in . Consequently, for every recursively enumerable language , there exists a propagating regular-controlled grammar with appearance checking with of the above form so that results from by erasing all rules in . In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper. [Copyright &y& Elsevier]

Abstract: We identify an abstract language for component software based on process algebra. Besides the usual operators for sequential, alternative and parallel composition, it has primitives for instantiating components and for deleting instances of components. We define an operational semantics for our language and give a type system in which types express quantitative information on the components involved in the execution of the expressions of the language. Included in this information is for each component the maximum number of instances that are simultaneously active during the execution of the expression. The type system is compositional by the novel use of ‘deficit types’. The type inference algorithm runs in time quadratic in the size of the input. We consider extensions of the language with loops and tail recursion, and with a scope mechanism. We illustrate the approach with some examples, one on UML diagram refinement and one on counting objects on the free store in C. [Copyright &y& Elsevier]

Abstract: We investigate in this article the operations of insertion and deletion working in a matrix-controlled manner. We show that this allows to us strictly increase the computational power: in the case of systems that are not computationally complete (with total size equal to 4), the computational completeness can be obtained by introducing the matrix control and using only binary matrices. [Copyright &y& Elsevier]