A framework to visualize equivalences between computational models of regular languages

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

The covering problem for linear context-free grammars

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

Vectorial languages and linear temporal logic

Determining for a given deterministic complete automaton the sequence of visited states while reading a given word is the core of important problems with automata-based solutions, such as approximate string matching. The main difficulty is to do this computation efficiently. Considering words as vectors and working on them using vectorial operations allows to solve the problem faster than using local operations.

In this paper, we show first that the set of vectorial operations needed by an algorithm representing a given automaton depends on the language accepted by the automaton. We give precise characterizations for star-free, solvable and regular languages using vectorial algorithms. We also study classes of languages associated with restricted sets of vectorial operations and relate them with languages defined by fragments of linear temporal logic.

Finally, we consider the converse problem of constructing an automaton from a given vectorial algorithm. As a byproduct, we show that the satisfiability problem for some extensions of LTL characterizing solvable and regular languages is PSPACE-complete.     

Regular Model Checking using Widening Techniques

In this paper, we consider symbolic model checking of safety properties of linear parametrized systems. Sets of configurations are represented by regular languages and actions by regular relations. Since the verification problem amounts to the computation of the reachability set, we focus on the computation of R^*(φ) for a regular relation R and a regular language φ. We present a technique called regular widening that allows, when it terminates, the computation of either the reachability set R^*(φ) of a system or the transitive closure R^* of a regular relation. We show that our method can be uniformly applied to several parametrized systems. Furthermore, we show that it is powerful enough to simulate some existing methods that compute either R^* or R^*(φ) for each R (resp. φ) belonging to a subclass of regular relations (resp. belonging to a subclass of regular languages).     

Coding properties of DNA languages

The computation language of a DNA-based system consists of all the words (DNA strands) that can appear in any computation step of the system. In this work we define properties of languages which ensure that the words of such languages will not form undesirable bonds when used in DNA computations. We give several characterizations of the desired properties and provide methods for obtaining languages with such properties. The decidability of these properties is addressed as well. As an application we consider splicing systems whose computation language is free of certain undesirable bonds and is generated by nearly optimal comma-free codes.     

On the role of complementation in implicit language equations and relations

We solve systems of boolean implicit equations and relations with union and complementation. If the languages are regular, we determine whether a system of implicit boolean equations or relations has solutions. If there is a solution, we provide an effective construction of a (regular) solution. We give representations for maximal and minimal solutions. Moreover, we also solve the problem of uniqueness of solutions as well as whether infinitely many solutions exist.     

Language equations for timed alternating finite automata

Traditionally, finite state automata are untimed or asynchronous models of computation in which only the ordering of events, not the time at which events occur, would affect the result of a computation. For real-time systems, it is important to augment these models of computation with a notion of time. For this purpose timed automata have become a powerful canonical model for describing timed behaviors and an effective tool for modeling real-time computations. In this paper, we extend the notion of timed alternating finite automata (TAFA), a class of alternating finite automata (AFA) extended with a finite set of real-valued clocks, and we present an algebraic interpretation of TAFA which parallels that of timed regular expressions and language equations. We further extend the equational representation of AFA to describe timed alternating finite automata, and explore solutions for such equations over time languages.     

Identifying Terminal Distinguishable Languages

We discuss new efficient learning algorithms for certain subclasses of regular and even linear languages based on the notion of terminal distinguishability introduced by Radhakrishnan and Nagaraja. The learning model we use is identification in the limit from positive samples as proposed by Gold and further studied by Angluin and many others. All classes we introduce in this paper are modifications of the language families TDRL (terminal distinguishable regular) and TDELL (terminal distinguishable even linear) defined by Radhakrishnan and Nagaraja. A tradeoff between the power of the language class and the time complexity of the identification algorithm is observed when the size of the underlying alphabet is considered as an additional parameter. Extending the classes of efficiently learnable languages is also important from the viewpoint of applications of the algorithms. One of these extensions is obtained basically by making use of the concept of control language which is known from formal language theory and has been employed for learning theoretic purposes in particular by Takada.     

Opacity of discrete event systems and its applications

In this paper, we investigate opacity of discrete event systems. We define two types of opacities: strong opacity and weak opacity. Given a general observation mapping, a language is strongly opaque if all strings in the language are confused with some strings in another language and it is weakly opaque if some strings in the language are confused with some strings in another language. We show that security and privacy of computer systems and communication protocols can be investigated in terms of opacity. In particular, two important properties in security and privacy, namely anonymity and secrecy, can be studied as special cases of opacity. We also show that by properly specifying the languages and the observation mapping, three important properties of discrete event systems, namely observability, diagnosability, and detectability, can all be reformulated as opacity. Thus, opacity has a wide range of applications. Also in this paper we provide algorithms for checking strong opacity and weak opacity for systems described by regular languages and having a generalized projection as the observation mapping.     

IFS与L系统的统一描述语言及其分类

为了更高效地表示分形图形,依据形式语言的文法结构及正则表达式的文法规则,通过引入代数运算,提出了一个能够对L系统和迭代函数系统(IFS)统一描述的语言代数系统。根据语言代数系统产生式的文法规则,将此系统的产生式集划分为五类。结合分形理论,此语言代数系统着重将DOL系统、迭代函数系统(IFS)、带凝聚集迭代函数系统(凝聚IFS)、随机迭代函数系统(IFSP)和再归迭代函数系统(RIFS)等进行描述,同时用此系统的正则表达式方程解将分形吸引子进行代数表示,并给出一些实例。通过实例表明,分形图形可以用该语言代数系统简单、明了、高效地表示。     

Characterization of co-observable languages and formulas for their super/sublanguages

We present fixed-point based characterization of several classes of co-observable languages that are of interest in the context of decentralized supervisory control of discrete-event systems, including C&P /spl or/ D&A co-observable languages, C&P co-observable languages, and D&A co-observable languages. We also provide formulas for computing super/sublanguages for each of these classes. In cases where the class of co-observable languages is not closed under intersection/union, we provide upper/lower bound of the super/sublanguage formula we present. The computation of super/sublanguages and also computation of their upper/lower bounds has lead to the introduction of other classes of co-observable languages, namely, strongly C&P co-observable languages, strongly D&A co-observable languages, locally observable languages, and strongly locally observable languages. Fixed-point based characterization of all the above language classes is also given, and their closure under intersection/union is investigated. We also study whether the fixed-point operator preserves prefix closure, relative closure (also called L/sub m/(G)-closure), and controllability.     

Parsers for indexed grammars

Three classes of parsable indexed grammars are defined. The new parsing mechanisms are derived by extending those that have been most successful for contextfree grammars, the LR and LL algorithms. Design criteria for the new grammar classes include membership decidability and unambiguity. We show that all three parsers operate in linear time for at least some grammars in our new classes. One of our new classes generates all the deterministic contextfree languages, along with some noncontextfree languages. We also show that the flag strings generated by indexed grammars are regular sets. This is done by showing that they can be generated by regular canonical systems.     

A visual representation of cellular automata-like systems

Cellular automata (CA) models and corresponding algorithms have a rich theoretical basis, and have also been used in a great variety of applications. A number of programming languages and systems have been developed to support the implementation of the CA models. However, these languages focus on computational and performance issues, and do not pay enough attention to programming productivity, usability, understandability, and other aspects of software engineering.In this paper, we describe a new special-purpose programming language developed for visual specification, presentation, and explanation of CA systems within a visual programming environment, as well as, for programming them. This language is based on using visual patterns, colors, and animation for representing the CA system structures and operations on these structures, and for performing editing and composing manipulations with corresponding software components. Examples of the CA algorithm representations and some details of the environment implementation are presented.     

Complexity of Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints Between Regular Open Terms

In this paper we study the satisfiability problem for language equations and constraints between regular open terms. We prove that: the constraint problem is PSPACE-complete, the regular language matching problem is EXPSPACE-complete even if we ask about satisfiability by regular languages, satisfiability of word-like language equations is in PSPACE, the finite solution problem is EXPSPACE-complete.     

Some relations between Markov algorithms and formal languages

Markov algorithms have received very little attention in the studies about formal languages, so the purpose of the present paper is twofold: i) to characterize languages in terms of Markov algorithms, and ii) to produce automatically Markov algorithms accepting or parsing languages generated by given grammars. We use a particular, although universal, subclass of Markov algorithms, which we call “pointer Markov algorithms»; we obtain a characterization of: i) regular, ii) deterministic context-free, and iii) type O languages, which is quite «natural» in terms of these algorithms. Furthermore, we show that, given a right linear or a strongLL(k) grammar, it is possible to produce automatically a pointer Markov algorithm parsing the language generated by the grammar. These constructions are particularly interesting because pointer Markov algorithms can be compiled conveniently into machine code programs.     

On the regularity of circular splicing languages: a survey and new developments

Circular splicing has been introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we focus on the relationship between regular circular languages and languages generated by finite circular splicing systems. We survey the known results towards a characterization of the intersection between these two classes and provide new contributions on the open problem of finding this characterization. First, we exhibit a non-regular circular language generated by a circular simple system thus disproving a known result in this area. Then we give new results related to a restrictive class of circular splicing systems, the marked systems. Precisely, we review in a graph theoretical setting the recently obtained characterization of marked systems generating regular circular languages. In particular, we define a slight variant of marked systems, that is the g-marked systems, and we introduce the graph associated with a g-marked system. We show that a g-marked system generates a regular circular language if and only if its associated graph is a cograph. Furthermore, we prove that the class of g-marked systems generating regular circular languages is closed under a complement operation applied to systems. We also prove that marked systems with self-splicing generate only regular circular languages.     

RECOGNITION CAN BE HARDER THAN PARSING

The work presented here attempts to bring out some fundamental concepts that underlie some known parsing algorithms, usually called chart or dynamic programming parsers, in the hope of guiding the design of similar algorithms for other formalisms that could be considered for describing the "surface" syntax of languages. The key idea is that chart parsing is essentially equivalent to a simple construction of the intersection of the language (represented by its grammar) with a regular set containing only the input sentence to be parsed (represented by a finite state machine). The resulting grammar for that intersection is precisely what is usually called a shared forest: it represents all parses of a syntactically ambiguous sentence. Since most techniques for processing ill-formed input can be modeled by considering a nonsingleton regular set of input sentences, we can expect to generalize these ill-formed input processing techniques to all parsers describable with our approach.     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.