Search

It is known that if a Büchi context-free language (BCFL) consists of scattered words, then there is an integer n, depending only on the language, such that the Hausdorff rank of each word in the language is bounded by n. Every BCFL is a Muller context-free language (MCFL). In the first part of the paper, we prove that an MCFL of scattered words is a BCFL iff the rank of every word in the language is bounded by an integer depending only on the language. Then we establish operational characterizations of the BCFLs of well-ordered and scattered words. We prove that a language is a BCFL consisting of well-ordered words iff it can be generated from the singleton languages containing the letters of the alphabet by substitution into ordinary context-free languages and the ⍵-power operation. We also establish a corresponding result for BCFLs of scattered words and define expressions denoting BCFLs of well-ordered and scattered words. In the final part of the paper we give some applications. [ABSTRACT FROM AUTHOR]

This paper is a continuation of our research work on state complexity of combined operations. Motivated by applications, we study the state complexities of two particular combined operations: catenation combined with star and catenation combined with reversal. We show that the state complexities of both of these combined operations are considerably less than the compositions of the state complexities of their individual participating operations. [ABSTRACT FROM AUTHOR]

This paper presents an approach to P system verification using the Spin model checker. It proposes a P system implementation in PROMELA, the modeling language accepted by SPIN. It also provides the theoretical background for transforming the temporal logic properties expressed for the P system into properties of the executable implementation. Furthermore, a comparison between P systems verification using SPIN and NUSMV is realized. The results obtained show that the PROMELA implementation is more adequate, especially for verifying more complex models, such as P systems that model ecosystems. [ABSTRACT FROM AUTHOR]

Hairpin completion is a formal operation inspired from DNA biochemistry. It is known that the (one step) hairpin completion of a regular language is linear context-free, but not regular in general. Further, it is decidable whether the (one step) hairpin completion of a regular language is regular. However, it is an open question whether the iterated hairpin completion of a regular language is regular, even if it is a singleton. If the word is a non-crossing α-word, there are results, but for crossing words there are no results. In this paper, we give necessary and sufficient conditions that the iterated hairpin completion of a given crossing (2, 2)-α-word in is regular. [ABSTRACT FROM AUTHOR]

This paper deals with insertability and mainly extractablity of codes. A code C is called insertable (or extractable) if the free submonoid C* generated by C satisfies if z, implies (or z, implies ). We show that a finite insertable code is a full uniform code. On the other hand there are many finite extractable codes which are not full uniform codes. We cannot still characterize the structures of infinite extractable codes. Here we give some results on the class of infix extractable codes. First, we consider a necessary and sufficient condition whether a given infix code C is extractable or not by using the syntactic graph of the code. Secondly, we investigate the extractability for the families of other related bifix codes. We newly define the bifix codes, called e(m)-codes and -codes, and refer to the extractability of them. [ABSTRACT FROM AUTHOR]

Positioned eco-grammar systems (PEG systems, for short) were introduced in [9]. Motivation of introducing positioned eco-grammar systems is an attempt to describe interplay between evolving environment and community of agents living in this environment whereas we focus on the positions of agents in the environment. PEG systems bring a new view to investigating interplay between community of agents and environment. Our approach allows to study local changes in evolving environment caused by agents moreover the position of the agent is strictly given by special symbol and we are able to predict its behavior and control the evolution of environment as well. In this paper we compare generative power of the PEG systems with three types of pure (regulated) grammars. [ABSTRACT FROM AUTHOR]

A language L is called the orthogonal shuffle of the language L1 with the language L2, along the trajectory set T if every word in L is uniquely obtained as the shuffle between a word in L1, a word in L2 along a trajectory word in T. In this paper we investigate properties of the orthogonal shuffle on trajectories, as well as several types of language equations using this language operation. As a corollary, we obtain several properties of orthogonal catenation, orthogonal literal shuffle and orthogonal insertion. [ABSTRACT FROM AUTHOR]

In this paper, the descriptional complexity of extended finite splicing systems is studied. These systems are known to generate exactly the class of regular languages. Upper and lower bounds are shown relating the size of these splicing systems, defined as the total length of the rules and the initial language of the system, to the size of their equivalent minimal nondeterministic finite automata (NFA). In addition, an accepting model of extended finite splicing systems is studied. Using this variant one can obtain systems which are more than polynomially more succinct than the equivalent NFA or generating extended finite splicing system. [ABSTRACT FROM AUTHOR]

Regular expressions are used in many practical applications. Practical regular expressions are commonly called "regex". It is known that regex are different from regular expressions. In this paper, we give regex a formal treatment. We make a distinction between regex and extended regex; while regex represent regular languages, extended regex represent a family of languages larger than regular languages. We prove a pumping lemma for the languages expressed by extended regex. We show that the languages represented by extended regex are incomparable with context-free languages and a proper subset of context-sensitive languages. Other properties of the languages represented by extended regex are also studied. [ABSTRACT FROM AUTHOR]

One of the new approaches to data classification uses prefix codes and finite state automata as representations of prefix codes. A prefix code is a (possibly infinite) set of strings such that no string is a prefix of another one. An important task driven by the need for the efficient storage of such automata in memory is the decomposition (in the sense of formal languages concatenation) of prefix codes into prime factors. We investigate properties of such prefix code decompositions. A prime decomposition is a decomposition of a prefix code into a concatenation of nontrivial prime prefix codes. A prefix code is prime if it cannot be decomposed into at least two nontrivial prefix codes. In the paper a linear time algorithm is designed which finds the prime decomposition F[sub 1]F[sub 2]…F[sub k] of a regular prefix code F given by its minimal deterministic automaton. Our results are especially interesting for infinite regular prefix codes. [ABSTRACT FROM AUTHOR]

A deterministic finite automaton (DFA) [formula] is called a cover automaton (DFCA) for a finite language L over some alphabet Σ if [formula], with l being the length of some longest word in L. Thus a word w ∈ Σ* is in L if and only if |w| ≤ l and [formula]. The DFCA [formula] is minimal if no DFCA for L has fewer states. In this paper, we present an algorithm which converts an n–state DFA for some finite language L into a corresponding minimal DFCA, using only O(n log n) time and O(n) space. The best previously known algorithm requires O(n[sup 2]) time and space. Furthermore, the new algorithm can also be used to minimize any DFCA, where the best previous method takes O(n[sup 4]) time and space. Since the required data structure is rather complex, an implementation in the common programming language C/C++ is also provided. [ABSTRACT FROM AUTHOR]

We present a generic aproach to the static analysis of concurrent programs with procedures. We model programs as communicating pushdown systems. It is known that typical dataflow problems for this model are undecidable, because the emptiness problem for the intersection of context-free languages, which is undecidable, can be reduced to them. In this paper we propose an algebraic framework for defining abstractions (upper approximations) of context-free languages. We consider two classes of abstractions: finite-chain abstractions, which are abstractions whose domains do not contain any infinite chains, and commutative abstractions corresponding to classes of languages that contain a word if and only if they contain all its permutations. We show how to compute such approximations by combining automata theoretic techniques with algorithms for solving systems of polynomial inequations in Kleene algebras. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of distributed ω-automata. Distributed ω-automata are a group of automata working in unison to accept an ω-language. We build the theory of distributed ω-automata for finite state automata and pushdown automata in different modes of cooperation like the t-mode, *-mode, = k-mode, ≤ k-mode and ≥ k-mode along with different acceptance criteria i.e. Büchi-, Muller-, Rabin- and Streett- acceptance criteria. We then analyze the acceptance power of such automata in all the above modes of cooperation and acceptance criteria. We present proofs that distributed ω-finite state automata do not have any additional power over ω-finite state automata in any of the modes of cooperation or acceptance criteria, while distributed ω-pushdown automata can accept languages not in CFL[sub ω]. We give proofs for the equivalence of all modes of cooperation and acceptance criteria in the case of distributed ω-pushdown automata. We show that the power of distributed ω-pushdown automata is equal to that of ω-Turing Machines. We also study the deterministic version of distributed ω-pushdown automata. Deterministic ω-pushdown automata accept only languages contained in CFL[sub ω] but distributed deterministic ω-pushdown automata can accept languages not in CFL[sub ω] and have the same power as their nondeterministic counterparts. We also define distributed completely deterministic ω-pushdown automata and analyze their power. [ABSTRACT FROM AUTHOR]

A bounded language L ⊆ x1*...xk (for some k ≥ 1 and not-necessarily distinct nonempty words x1,...,Xk) is bounded semilinear if the set Q{L) = {(i1,...,ik) | x1¹...xkk ∈ L} is semilinear. We give characterizations of bounded semilinear languages in terms of one-way and two-way deterministic counter machines. [ABSTRACT FROM AUTHOR]

We investigate the descriptional complexity of limited Lindenmayer systems and their deterministic and tabled variants with respect to the number of rules and the number of symbols. In this part, we confine ourselves to propagating limited Lindenmayer systems. We determine the decrease of complexity when the generative capacity is increased. For incomparable families, we give languages that can be described more efficiently in either of these families than in the other. [ABSTRACT FROM AUTHOR]

In this paper finite state recognizers are considered as unary tree recognizers with unary operational symbols. We introduce translation recognizers of a tree recognizer, which are finite state recognizers whose operations are the elementary translations of the underlying algebra of the considered tree recognizer. In terms of translation recognizers we give general conditions under which a class of recognizable tree languages with a given property can be determined by a class of monoids determining the class of string languages having the same property. [ABSTRACT FROM AUTHOR]

Extended finite automata are finite state automata equipped with the additional ability to apply an operation on the currently remaining input word, depending on the current state. Hybrid extended finite automata can choose from a finite set of such operations. In this paper, five word operations are taken into consideration which always yield letter-equivalent results, namely reversal and shift operations. The computational power of those machines is investigated, locating the corresponding families of languages in the Chomsky hierarchy. Furthermore, different types of hybrid extended finite automata, defined by the set of operations they are allowed to apply, are compared with each other, demonstrating that there exist dependencies and independencies between the input manipulating operations. [ABSTRACT FROM AUTHOR]

In this paper, we present a process algebra aimed at modelling PKI-based systems. The new language, SPIKY, extends the spi-calculus by adding primitives for the retrieval of certified/uncertified public keys as well as private keys belonging to users of the PKI-based system. SPIKY also formalises the notion of process ownership by PKI users, which is necessary in controlling the semantics of the key retrieval capabilities. We also construct a static analysis for SPIKY that captures the property of term substitutions resulting from message-passing and PKI/cryptographic operations. This analysis is shown to be safe and computable. Finally, we use the analysis to define the term secrecy and peer participation properties for a couple of examples of authentication protocols. [ABSTRACT FROM AUTHOR]

The paper investigates two-dimensional recognizable languages that are defined by the so-called "dot systems" that are special subgroups of (ℤ/2ℤ)ℤ2. The dot shapes that provide directional transitivity or mixing for the related language are investigated. It is shown that languages defined by parallelogram shapes fail to be transitive in the direction of a defining vector and hence fail to be mixing, while certain triangular shapes guarantee that the factor language of the associated dot system will be mixing. Dot systems belong to a class of two-dimensional shift spaces that have a factor language such that every admissable block can be extended to a configuration of the entire plane. For this class of shift spaces we introduce a finite graph (i.e., a finite state automaton) that recognizes two-dimensional local languages, then show that certain transitivity properties may be observed from the structure of the finite graph. [ABSTRACT FROM AUTHOR]

We show that the class of Event Clock Automata [2] admit a logical characterisation via an unrestricted monadic second order logic interpreted over timed words. The result is interesting in that it provides an unrestricted yet decidable logical characterisation of a non-trivial class of timed languages. A timed temporal logic considered earlier in the literature [11] is shown to be expressively complete with respect to the monadic logic. [ABSTRACT FROM AUTHOR]

We show that it is undecidable whether or not two finite substitutions are equivalent on the fixed regular language ab*c. This gives an unexpected answer to a question proposed in 1985 by Culik II and Karhumäki. At the same time it can be seen as the final result in a series of undecidability results for finite transducers initiated in 1968 by Griffiths. An application to systems of equations over finite languages is given. [ABSTRACT FROM AUTHOR]

We propose the one-way jumping finite automaton model, restricting the jumping relation of the recently introduced jumping finite automaton so that the machine can only jump over symbols it cannot process in its current state. The reading head of a one-way jumping finite automaton moves deterministically in one direction within the input word, whereas movement of the reading head of jumping finite automaton is non-deterministic. The class of languages accepted by one-way jumping finite automata is different from that of jumping finite automata, in particular, it includes all regular languages, as opposed to the latter. We study one-way jumping finite automata and obtain closure properties, a pumping lemma, and separation results with respect to the classical language classes of the Chomsky hierarchy. [ABSTRACT FROM AUTHOR]

We introduce the inner palindromic closure as a new operation ♠, which consists in expanding a factor u to the left or right by a non-empty word v such that vu or uv, respectively, is a palindrome of minimal length. We investigate several language theoretic properties of the iterated inner palindromic closure ♠*(w) = Ui≥0 ♠i(w) of a word w. [ABSTRACT FROM AUTHOR]

We study FAD-languages, which are regular languages defined by finite sets of forbidden factors, together with their 'canonical' recognizing automata. We are mainly interested in the possible asymptotic orders of growth for such languages. We analyze certain simplifications of sets of forbidden factors and show that they 'almost' preserve the canonical automata. Using this result and structural properties of canonical automata, we describe an algorithm that effectively lists all canonical automata having a sink strong component isomorphic to a given digraph, or reports that no such automata exist. This algorithm can be used, in particular, to prove the existence of a FAD-language over a given alphabet with a given exponential growth rate. On the other hand, we give an example showing that the algorithm cannot prove non-existence of a FAD-language having a given growth rate. Finally, we provide some examples of canonical automata with a nontrivial condensation graph and of FAD-languages with a 'complex' order of growth. [ABSTRACT FROM AUTHOR]

The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The distance between languages L1 and L2 is the smallest edit-distance between string wi ∈ Li, i = 1, 2. We consider the problem of computing the edit-distance of a given regular language and a given context-free language. First, we present an algorithm that finds for the languages an optimal alignment, that is, a sequence of edit operations that transforms a string in one language to a string in the other. The length of the optimal alignment, in the worst case, is exponential in the size of the given grammar and finite automaton. Then, we investigate the problem of computing only the edit-distance of the languages without explicitly producing an optimal alignment. We design a polynomial time algorithm that calculates the edit-distance based on unary homomorphisms. [ABSTRACT FROM AUTHOR]

We shall show that (i) there exists a binary NP-complete language such that its unary coded version is in ASPACE( n), (ii) if P ≠ NP, there exists a binary language such that its unary version is in ASPACE( n), while the language itself is not in ASPACE( n). As a consequence, under assumption that P ≠ NP, the standard space translation between unary and binary languages does not work for alternating machines with small space; the equivalence is valid only if s(n) ∈ Ω(n). This is quite different from deterministic and nondeterministic machines, for which the corresponding equivalence holds for each s(n) ∈ Ω( n), and hence for s( n) ∈ Ω( n). Under assumption that NP ≠ co-NP, we also show that binary versions of unary languages in ASPACE( n) form a complexity class not contained in NP. [ABSTRACT FROM AUTHOR]

The quotient complexity of a regular language L, which is the same as its state complexity, is the number of left quotients of L. An atom of a non-empty regular language L with n quotients is a non-empty intersection of the n quotients, which can be uncomplemented or complemented. An NFA is atomic if the right language of every state is a union of atoms. We characterize all reduced atomic NFAs of a given language, i.e., those NFAs that have no equivalent states. We prove that, for any language L with quotient complexity n, the quotient complexity of any atom of L with r complemented quotients has an upper bound of 2n − 1 if r = 0 or r = n; for 1 ≤ r ≤ n − 1 the bound is For each n ≥ 2, we exhibit a language with 2n atoms which meet these bounds. [ABSTRACT FROM AUTHOR]

We introduce E-equivalence, which is a straightforward generalization of almost-equivalence. While almost-equivalence asks for ordinary equivalence up to a finite number of exceptions, in E-equivalence these exceptions or errors must belong to a (regular) set E. The computational complexity of deterministic finite automata (DFAs) minimization problems and their variants w.r.t. almost- and E-equivalence are studied. We show that there is a significant difference in the complexity of problems related to almost-equivalence, and those related to E-equivalence. Moreover, since hyper-minimal and E-minimal automata are not necessarily unique (up to isomorphism as for minimal DFAs), we consider the problem of counting the number of these minimal automata. [ABSTRACT FROM AUTHOR]

The quotient complexity, also known as state complexity, of a regular language is the number of distinct left quotients of the language. The quotient complexity of an operation is the maximal quotient complexity of the language resulting from the operation, as a function of the quotient complexities of the operands. The class of star-free languages is the smallest class containing the finite languages and closed under boolean operations and concatenation. We prove that the tight bounds on the quotient complexities of union, intersection, difference, symmetric difference, concatenation and star for starfree languages are the same as those for regular languages, with some small exceptions, whereas Zn -- 1 is a lower bound for reversal. [ABSTRACT FROM AUTHOR]

We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has α states, for all n and α satisfying n ≤ α ≤ 2n. A number α not satisfying this condition is called a magic number (for n). It was shown that no magic numbers exist for general regular languages, whereas trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, star-free languages, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic. [ABSTRACT FROM AUTHOR]

An Spiking Neural P system with anti-spikes uses two types of objects called spikes and anti-spikes which can encode binary digits in a natural way. The step when system emits a spike or an anti-spike is associated with symbol 1 and 0, respectively. Here we consider these computing devices as language generators. They allow non-determinism between the rules ac → a and ac → ā, c ϵ ℕ, thus help to generate languages which cannot be generated using simple SN P systems. [ABSTRACT FROM AUTHOR]

The simulation of weak restarting automata, i.e., classical restarting automata accepting exactly the regular languages, by finite automata is studied. Some of the trade-offs in the number of states when changing the representation are known. Here we continue the investigation in order to draw an almost complete picture of the descriptional power gained in the additional structural resources of weak restarting automata. In particular, for det-RR(1)-simulations of nondeterministic finite automata we obtain the same tight bounds as for simulations of R(1)-automata, though in some cases the latter class is much more efficient than the former. Moreover, the DFA-simulation of det-RR(1)-automata is considered. The shown bounds are of factorial order and are tight. The constructions are via alternating finite automata to DFAs. So, in addition, an upper bound for the AFA-simulation is obtained. [ABSTRACT FROM AUTHOR]

Finitely subsequential transducers are efficient finite-state transducers with a finite number of final outputs and are used in a variety of applications. Not all transducers admit equivalent finitely subsequential transducers however. We briefly describe an existing generalized determinization algorithm for finitely subsequential transducers and give the first characterization of finitely subsequentiable transducers, transducers that admit equivalent finitely subsequential transducers. Our characterization shows the existence of an efficient algorithm for testing finite subsequentiability. We have fully implemented the generalized determinization algorithm and the algorithm for testing finite subsequentiability. We report experimental results showing that these algorithms are practical in large-vocabulary speech recognition applications. The theoretical formulation of our results is the equivalence of the following three properties for finite-state transducers: determinizability in the sense of the generalized algorithm, finite subsequentiability, and the twins property. [ABSTRACT FROM AUTHOR]

We investigate the descriptional complexity of operations on finite and infinite regular languages over unary and arbitrary alphabets. The languages are represented by nondeterministic finite automata (NFA). In particular, we consider Boolean operations, catenation operations – concatenation, iteration, λ-free iteration – and the reversal. Most of the shown bounds are tight in the exact number of states, i.e. the number is sufficient and necessary in the worst case. Otherwise tight bounds in the order of magnitude are shown. [ABSTRACT FROM AUTHOR]

An approach for systematically modifying the semantics of programming languages by semantics modifiers is described. Semantics modifiers are a class of programs that allow the development of general and reusable "semantics components". Language independence is achieved through the interpretive approach: an interpreter serves as a mediator between the new language and the language for which the non-standard semantics was implemented. Inverse computation, equivalence transformation and neighborhood analysis are shown to be semantics modifiers. Experiments with these modifiers show the computational feasibility of this approach. Seven modifier projections are given which allow the efficient implementation of non-standard interpreters and non-standard compilers by program specialization or other powerful program transformation methods. [ABSTRACT FROM AUTHOR]