Loading [MathJax]/jax/output/CommonHTML/jax.js
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

SEARCH GUIDE  Download Search Tip PDF File

  Bestsellers

  • articleNo Access

    Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata Over Small Alphabets

    It is shown that a two-way deterministic finite automaton (2DFA) with n states over an alphabet Σ can be transformed to an equivalent one-way automaton (1DFA) with |Σ|φ(n)+1 states, where φ(n)=maxn1k=1knk+1=nnnlnlnnlnn+O(nlnn). This reflects the fact that, by keeping the last processed symbol a in memory, the simulating 1DFA can remember one of k states in which the automaton moves by a to the right, and a function that maps nk states moving to the left to k states moving to the right; cf. ca. nn functions in the classical construction. A close lower bound of φ(n) states is established using a 2-symbol alphabet, with witness languages defined by direction-determinate 2DFA. The same lower bound is also achieved with witness languages defined by sweeping 2DFA, at the expense of using a 5-symbol alphabet. In addition, the complexity of transforming a sweeping or a direction-determinate 2DFA to a 1DFA is shown to be exactly φ(n).

  • articleOpen Access

    Image-Binary Automata

    We introduce a certain restriction of weighted automata over the rationals, called image-binary automata. We show that such automata accept the regular languages, can be exponentially more succinct than corresponding NFAs, and allow for polynomial complementation, union, and intersection. This compares favourably with unambiguous automata whose complementation requires a superpolynomial state blowup. We also study an infinite-word version, image-binary Büchi automata. We show that such automata are amenable to probabilistic model checking, similarly to unambiguous Büchi automata. We provide algorithms to translate k-ambiguous Büchi automata to image-binary Büchi automata, leading to model-checking algorithms with optimal computational complexity.

  • articleNo Access

    Compressed Structures for Partial Derivative Automata Constructions

    The partial derivative automaton (𝒜PD) is an elegant simulation of a regular expression. Although it is, in general, smaller than the position automaton (𝒜POS), the algorithms that build 𝒜PD in quadratic worst-case time first compute 𝒜POS. Asymptotically, and on average for the uniform distribution, the size of 𝒜PD is half the size of 𝒜POS, being both linear on the size of the expression. We address the construction of 𝒜PD efficiently, on average, avoiding the computation of 𝒜POS. The expression and the set of its partial derivatives are represented by a directed acyclic graph with shared common subexpressions. We develop an algorithm for building 𝒜PDs from expressions in strong star normal form of size n that runs, on average, in time that asymptotically behaves as n3/24log(n), and space as n3/2/(logn)3/4. Empirical results corroborate its good practical performance.

  • articleNo Access

    Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems

    We consider general computational models: one-way and two-way finite automata, and logarithmic space Turing machines, all equipped with an auxiliary data structure (ADS). The definition of an ADS is based on the language of protocols of work with the ADS. We describe the connection of automata-based models with “Balloon automata” that are another general formalization of automata equipped with an ADS presented by Hopcroft and Ullman in 1967. This definition establishes the connection between the non-emptiness problem for one-way automata with ADS, languages recognizable by nondeterministic log-space Turing machines equipped with the same ADS, and a regular realizability problem (NRR) for the language of ADS’ protocols. The NRR problem is to verify whether the regular language on the input has a non-empty intersection with the language of protocols. The computational complexity of these problems (and languages) is the same up to log-space reductions.

  • articleNo Access

    Binary Coded Unary Regular Languages

    {0,1} is a binary coded unary regular language, if there exists a unary regular language {a} such that ax is in  if and only if the binary representation of x is in . If a unary language  is accepted by a minimal deterministic finite automaton (DFA) 𝒜 with n states, then its binary coded version  is regular and can be accepted by a DFA 𝒜 using at most n states, but at least 1+logn states. There are witness languages matching these upper and lower bounds exactly, for each n.

    More precisely, if 𝒜 uses σ0 states in the initial segment and μ2 states in the loop, where μ is odd and 0, then the minimal 𝒜 for  consists of a preamble with at most σ but at least max{1,1+logσ} states, except for σ=0 with no preamble, and a kernel with at most μ2 but at least μ+ states. Also these lower bounds are matched exactly by witness languages, for each σ,μ,. If the length of the loop is fixed, the size of the preamble is bounded by O(σ/logσ).

    The conversion in the opposite way is not always granted: there are binary regular languages the unary versions of which are not even context free.

    The conversion of a unary nondeterministic finite automaton (NFA) to a binary NFA uses O(n2) states and introduces a binary version of Chrobak normal form.

  • articleNo Access

    Operations on Boolean and Alternating Finite Automata

    We investigate the complexity of basic regular operations on languages represented by Boolean and alternating finite automata. We get tight upper bounds m+n and m+n+1 for union, intersection, and difference, 2m+n and 2m+n+1 for concatenation, 2n+n and 2n+n+1 for square, m and m+1 for left quotient, 2m and 2m+1 for right quotient. We also show that in both models, the complexity of complementation and symmetric difference is n and m+n, respectively, while the complexity of star and reversal is 2n. All our witnesses are described over a unary or binary alphabets, and whenever we use a binary alphabet, it is always optimal. We also show that the tight upper bound for the conversion of alternating finite automata into nondeterministic finite automata with a unique initial state is 2n+1. Some of our results provide answers to open problems stated by Fellah et al. [5].

  • articleNo Access

    GENERIC ∊-REMOVAL AND INPUT ∊-NORMALIZATION ALGORITHMS FOR WEIGHTED TRANSDUCERS

    We present a new generic ∊-removal algorithm for weighted automata and transducers defined over a semiring. The algorithm can be used with any semiring covered by our framework and works with any queue discipline adopted. It can be used in particular in the case of unweighted automata and transducers and weighted automata and transducers defined over the tropical semiring. It is based on a general shortest-distance algorithm that we briefly describe. We give a full description of the algorithm including its pseudocode and its running time complexity, discuss the more efficient case of acyclic automata, an on-the-fly implementation of the algorithm and an approximation algorithm in the case of the semirings not covered by our framework. We illustrate the use of the algorithm with several semirings. We also describe an input ∊-normalization algorithm for weighted transducers based on the general shortest-distance algorithm. The algorithm, which works with all semirings covered by our framework, admits an on-the-fly implementation.

  • articleNo Access

    UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

    In this paper we give the cost, in terms of states, of some basic operations (union, intersection, concatenation, and Kleene star) on regular languages in the unary case (where the alphabet contains only one symbol). These costs are given by explicitly determining the number of states in the noncyclic and cyclic parts of the resulting automata. Furthermore, we prove that our bounds are optimal. We also present an interesting connection to Jacobsthal's function from number theory.

  • articleNo Access

    A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM

    We consider the problem of labeling a directed multigraph so that it becomes a synchronized finite automaton, as an ultimate goal to solve the famous Road Coloring Conjecture, cf. [1,2]. We introduce a relabeling method which can be used for a large class of automata to improve their 'degree of synchronization'. This allows, for example, to formulate the conjecture in several equivalent ways.

  • articleNo Access

    The Equivalence Problem of Finite Substitutions on ab*c, with Applications

    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.

  • articleNo Access

    LINEAR-TIME PRIME DECOMPOSITION OF REGULAR PREFIX CODES

    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 F1F2…Fk of a regular prefix code F given by its minimal deterministic automaton. Our results are especially interesting for infinite regular prefix codes.

  • articleNo Access

    FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS

    We present a technique based on the construction of finite automata to prove termination of string rewriting systems. Using this technique the tools Matchbox and TORPA are able to prove termination of particular string rewriting systems completely automatically for which termination was considered to be very hard until recently.

  • articleNo Access

    DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY

    In this paper, we study the tradeoffs in descriptional complexity of NFA (nondeterministic finite automata) of various amounts of ambiguity. We say that two classes of NFA are separated if one class can be exponentially more succinct in descriptional sizes than the other. New results are given for separating DFA (deterministic finite automata) from UFA (unambiguous finite automata), UFA from MDFA (DFA with multiple initial states) and UFA from FNA (finitely ambiguous NFA). We present a family of regular languages that we conjecture to be a good candidate for separating FNA from LNA (linearly ambiguous NFA).

  • articleNo Access

    A FRAMEWORK FOR THE DYNAMIC IMPLEMENTATION OF FINITE AUTOMATA FOR PERFORMANCE ENHANCEMENT

    The aim of this work is to provide a model for the dynamic implementation of finite automata for enhanced performance. Investigations have shown that hardcoded finite automata outperforms the traditional table-driven implementation up to some threshold. Moreover, the kind of string being recognized plays a major role in the overall processing speed of the string recognizer. Various experiments are depicted to show when the advantages of using hardcoding as basis for implementing finite automata (instead of using the classical table-driven approach) become manifest. The model, a dynamic algorithm that combines both hardcoding and table-driven is introduced.

  • articleNo Access

    HYBRID EXTENDED FINITE AUTOMATA

    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.

  • articleNo Access

    AN EFFICIENT ALGORITHM TO TEST WHETHER A BINARY AND PROLONGEABLE REGULAR LANGUAGE IS GEOMETRICAL

    Our aim is to present an efficient algorithm that checks whether a binary regular language is geometrical or not, based on specific properties of its minimal deterministic automaton. Geometrical languages have been introduced in the framework of off-line temporal validation of real-time softwares. Actually, validation can be achieved through both a model based on regular languages and a model based on discrete geometry. Geometrical languages are intended to develop a link between these two models. The regular case is of practical interest regarding to implementation features, which motivates the design of an efficient geometricity test addressing the family of regular languages.

  • articleNo Access

    THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS

    We summarize results on the complexity of regular(-like) expressions and tour a fragment of the literature. In particular we focus on the descriptional complexity of the conversion of regular expressions to equivalent finite automata and vice versa, to the computational complexity of problems on regular-like expressions such as, e.g., membership, inequivalence, and non-emptiness of complement, and finally on the operation problem measuring the required size for transforming expressions with additional language operations (built-in or not) into equivalent ordinary regular expressions.

  • articleNo Access

    STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION

    In this paper, we study the state complexities of two particular combinations of operations: catenation combined with union and catenation combined with intersection. We show that the state complexity of the former combined operation is considerably less than the mathematical composition of the state complexities of catenation and union, while the state complexity of the latter one is equal to the mathematical composition of the state complexities of catenation and intersection.

  • articleNo Access

    IT IS NL-COMPLETE TO DECIDE WHETHER A HAIRPIN COMPLETION OF REGULAR LANGUAGES IS REGULAR

    The hairpin completion is an operation on formal languages which is inspired by the hairpin formation in biochemistry. Hairpin formations occur naturally within DNA-computing. It has been known that the hairpin completion of a regular language is linear context-free, but not regular, in general. However, for some time it is was open whether the regularity of the hairpin completion of a regular language is decidable. In 2009 this decidability problem has been solved positively in [5] by providing a polynomial time algorithm. In this paper we improve the complexity bound by showing that the decision problem is actually NL-complete. This complexity bound holds for both, the one-sided and the two-sided hairpin completions.

  • articleNo Access

    THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES

    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.