Topic overview

Formal Languages and Automata Theory

714 works1476 researchers0 institutions

Topic snapshot

What this area looks like now

714works

1476authors

0experts visible

0communities

Next steps

Move from topic reading into action

The graph preview below keeps the nearby papers, people and communities visible in the same reading flow.

Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2011arXiv

Traced communication complexity of cellular automata

We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansiveness, entropy and give the asymptotic communication complexity of most elementary cellular automata.

preprint2011arXiv

Reduction of fuzzy automata by means of fuzzy quasi-orders

In our recent paper we have established close relationships between state reduction of a fuzzy recognizer and resolution of a particular system of fuzzy relation equations. In that paper we have also studied reductions by means of those solutions which are fuzzy equivalences. In this paper we will see that in some cases better reductions can be obtained using the solutions of this system that are fuzzy quasi-orders. Generally, fuzzy quasi-orders and fuzzy equivalences are equally good in the state reduction, but we show that right and left invariant fuzzy quasi-orders give better reductions than right and left invariant fuzzy equivalences. We also show that alternate reductions by means of fuzzy quasi-orders give better results than alternate reductions by means of fuzzy equivalences. Furthermore we study a more general type of fuzzy quasi-orders, weakly right and left invariant ones, and we show that they are closely related to determinization of fuzzy recognizers. We also demonstrate some applications of weakly left invariant fuzzy quasi-orders in conflict analysis of fuzzy discrete event systems.

preprint2011arXiv

On minimising automata with errors

The problem of k-minimisation for a DFA M is the computation of a smallest DFA N (where the size |M| of a DFA M is the size of the domain of the transition function) such that their recognized languages differ only on words of length less than k. The previously best algorithm, which runs in time O(|M| log^2 n) where n is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster O(|M| log n) algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a k-minimal DFA for each k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA M and numbers k and m, it is NP-hard to decide whether there exists a k-minimal DFA N differing from DFA M on at most m words. A similar result holds for hyper-minimisation of DFAs in general: Given a DFA M and numbers s and m, it is NP-hard to decide whether there exists a DFA N with at most s states such that DFA M and N differ on at msot m words.

preprint2011arXiv

Free inductive K-semialgebras

We consider rational power series over an alphabet $Σ$ with coefficients in a ordered commutative semiring $K$ and characterize them as the free ordered $K$-semialgebras in various classes of ordered $K$-semialgebras equipped with a star operation satisfying the least pre-fixed point rule and/or its dual. The results are generalizations of Kozen's axiomatization of regular languages.

preprint2011arXiv

Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2=x^3

In this paper we investigate the word problem of the free Burnside semigroup satisfying x^2=x^3 and having two generators. Elements of this semigroup are classes of equivalent words. A natural way to solve the word problem is to select a unique "canonical" representative for each equivalence class. We prove that overlap-free words and so-called almost overlap-free words (this notion is some generalization of the notion of overlap-free words) can serve as canonical representatives for corresponding equivalence classes. We show that such a word in a given class, if any, can be efficiently found. As a result, we construct a linear-time algorithm that partially solves the word problem for the semigroup under consideration.

preprint2011arXiv

Nondeterministic automata: equivalence, bisimulations, and uniform relations

In this paper we study the equivalence of nondeterministic automata pairing the concept of a bisimulation with the recently introduced concept of a uniform relation. In this symbiosis, uniform relations serve as equivalence relations which relate states of two possibly different nondeterministic automata, and bisimulations ensure compatibility with the transitions, initial and terminal states of these automata. We define six types of bisimulations, but due to the duality we discuss three of them: forward, backward-forward, and weak forward bisimulations. For each od these three types of bisimulations we provide a procedure which decides whether there is a bisimulation of this type between two automata, and when it exists, the same procedure computes the greatest one. We also show that there is a uniform forward bisimulation between two automata if and only if the factor automata with respect to the greatest forward bisimulation equivalences on these automata are isomorphic. We prove a similar theorem for weak forward bisimulations, using the concept of a weak forward isomorphism instead of an isomorphism. We also give examples that explain the relationships between the considered t

preprint2011arXiv

Finite Orbits of Language Operations

We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure.

preprint2011arXiv

A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars

The main aim of the paper is to give a short self-contained proof of the decidability of language equivalence for deterministic pushdown automata, which is the famous problem solved by G. Senizergues, for which C. Stirling has derived a primitive recursive complexity upper bound. The proof here is given in the framework of first-order grammars, which seems to be particularly apt for the aim. An appendix presents a modification of Stirling's approach, yielding a complexity bound of the form tetr(2,g(n)) where tetr is the (nonelementary) operator of iterated exponentiation (tetration) and g is an elementary function of the input size.

preprint2011arXiv

Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata

In this report we study the problem of minimising deterministic automata over finite and infinite words. Deterministic finite automata are the simplest devices to recognise regular languages, and deterministic Buchi, Co-Buchi, and parity automata play a similar role in the recognition of ω-regular languages. While it is well known that the minimisation of deterministic finite and weak automata is cheap, the complexity of minimising deterministic Buchi and parity automata has remained an open challenge. We establish the NP-completeness of these problems. A second contribution of this report is the introduction of relaxed minimisation of deterministic finite automata. Like hyper-minimisation, relaxed minimisation allows for some changes in the language of the automaton: We seek a smallest automaton that, when used as a monitor, provides a wrong answer only a bounded number of times in any run of a system. We argue that minimisation of finite automata, hyper-minimisation, relaxed minimisation, and the minimisation of deterministic Buchi (or Co-Buchi) automata are operations of increasing reduction power, as the respective equivalence relations on automata become coarser from left to r

preprint2011arXiv

On the capabilities of grammars, automata, and transducers controlled by monoids

During the last decades, classical models in language theory have been extended by control mechanisms defined by monoids. We study which monoids cause the extensions of context-free grammars, finite automata, or finite state transducers to exceed the capacity of the original model. Furthermore, we investigate when, in the extended automata model, the nondeterministic variant differs from the deterministic one in capacity. We show that all these conditions are in fact equivalent and present an algebraic characterization. In particular, the open question of whether every language generated by a valence grammar over a finite monoid is context-free is provided with a positive answer.

preprint2011arXiv

Decidability and Shortest Strings in Formal Languages

Given a formal language L specified in various ways, we consider the problem of determining if L is nonempty. If L is indeed nonempty, we find upper and lower bounds on the length of the shortest string in L.

preprint2011arXiv

Remarks on separating words

The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length <= n (by accepting one and rejecting the other). In this paper we survey what is known and unknown about the problem, consider some variations, and prove several new results.

preprint2011arXiv

On primary and secondary repetitions in words

Combinatorial properties of maximal repetitions (runs) in formal words are studied. We classify all maximal repetitions in a word as primary and secondary where the set of all primary repetitions determines all the other repetitons in the word. Essential combinatorial properties of primary repetitions are established.

preprint2011arXiv

On Non-Complete Sets and Restivo's Conjecture

A finite set S of words over the alphabet A is called non-complete if Fact(S*) is different from A*. A word w in A* - Fact(S*) is said to be uncompletable. We present a series of non-complete sets S_k whose minimal uncompletable words have length 5k^2 - 17k + 13, where k > 3 is the maximal length of words in S_k. This is an infinite series of counterexamples to Restivo's conjecture, which states that any non-complete set possesses an uncompletable word of length at most 2k^2.

preprint2011arXiv

Streaming algorithms for language recognition problems

We study the complexity of the following problems in the streaming model. Membership testing for \DLIN We show that every language in \DLIN\ can be recognised by a randomized one-pass $O(\log n)$ space algorithm with inverse polynomial one-sided error, and by a deterministic p-pass $O(n/p)$ space algorithm. We show that these algorithms are optimal. Membership testing for \LL$(k)$ For languages generated by \LL$(k)$ grammars with a bound of $r$ on the number of nonterminals at any stage in the left-most derivation, we show that membership can be tested by a randomized one-pass $O(r\log n)$ space algorithm with inverse polynomial (in $n$) one-sided error. Membership testing for \DCFL We show that randomized algorithms as efficient as the ones described above for \DLIN\ and $\LL(k)$ (which are subclasses of \DCFL) cannot exist for all of \DCFL: there is a language in \VPL\ (a subclass of \DCFL) for which any randomized p-pass algorithm with error bounded by $ε< 1/2$ must use $Ω(n/p)$ space. Degree sequence problem We study the problem of determining, given a sequence $d_1, d_2,..., d_n$ and a graph $G$, whether the degree sequence of $G$ is precisely $d_1, d_2,..., d_n$. We give a ra

preprint2011arXiv

On the regularity of iterated hairpin completion of a single word

Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand $w = xαy \calpha$, and outputs $w' = x αy \barα \bar{x}$, where $\bar{x}$ denotes the Watson-Crick complement of $x$. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words $α$ and $\calpha$ that initiate hairpin completion and how they are scattered, we classify the set of all words $w$. For some basic classes of words $w$ containing small numbers of occurrences of $α$ and $\calpha$, we prove that the iterated hairpin completion of $w$ is regular. For other classes with higher numbers of occurrences of $α$ and $\calpha$, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.

preprint2011arXiv

Pushing undecidability of the isolation problem for probabilistic automata

This short note aims at proving that the isolation problem is undecidable for probabilistic automata with only one probabilistic transition. This problem is known to be undecidable for general probabilistic automata, without restriction on the number of probabilistic transitions. In this note, we develop a simulation technique that allows to simulate any probabilistic automaton with one having only one probabilistic transition.

preprint2011arXiv

IUPC: Identification and Unification of Process Constraints

Business Process Compliance (BPC) has gained significant momentum in research and practice during the last years. Although many approaches address BPC, they mostly assume the existence of some kind of unified base of process constraints and focus on their verification over the business processes. However, it remains unclear how such an inte- grated process constraint base can be built up, even though this con- stitutes the essential prerequisite for all further compliance checks. In addition, the heterogeneity of process constraints has been neglected so far. Without identification and separation of process constraints from domain rules as well as unification of process constraints, the success- ful IT support of BPC will not be possible. In this technical report we introduce a unified representation framework that enables the identifica- tion of process constraints from domain rules and their later unification within a process constraint base. Separating process constraints from domain rules can lead to significant reduction of compliance checking effort. Unification enables consistency checks and optimizations as well as maintenance and evolution of the constraint base on the oth

preprint2011arXiv

Simulating Spiking Neural P systems without delays using GPUs

We present in this paper our work regarding simulating a type of P system known as a spiking neural P system (SNP system) using graphics processing units (GPUs). GPUs, because of their architectural optimization for parallel computations, are well-suited for highly parallelizable problems. Due to the advent of general purpose GPU computing in recent years, GPUs are not limited to graphics and video processing alone, but include computationally intensive scientific and mathematical applications as well. Moreover P systems, including SNP systems, are inherently and maximally parallel computing models whose inspirations are taken from the functioning and dynamics of a living cell. In particular, SNP systems try to give a modest but formal representation of a special type of cell known as the neuron and their interactions with one another. The nature of SNP systems allowed their representation as matrices, which is a crucial step in simulating them on highly parallel devices such as GPUs. The highly parallel nature of SNP systems necessitate the use of hardware intended for parallel computations. The simulation algorithms, design considerations, and implementation are presented. Finall

preprint2011arXiv

Geometric Semigroup Theory

Geometric semigroup theory is the systematic investigation of finitely-generated semigroups using the topology and geometry of their associated automata. In this article we show how a number of easily-defined expansions on finite semigroups and automata lead to simplifications of the graphs on which the corresponding finite semigroups act. We show in particular that every finite semigroup can be finitely expanded so that the expansion acts on a labeled directed graph which resembles the right Cayley graph of a free Burnside semigroup in many respects.

preprint2011arXiv

Measuring and Synthesizing Systems in Probabilistic Environments

Often one has a preference order among the different systems that satisfy a given specification. Under a probabilistic assumption about the possible inputs, such a preference order is naturally expressed by a weighted automaton, which assigns to each word a value, such that a system is preferred if it generates a higher expected value. We solve the following optimal-synthesis problem: given an omega-regular specification, a Markov chain that describes the distribution of inputs, and a weighted automaton that measures how well a system satisfies the given specification under the given input assumption, synthesize a system that optimizes the measured value. For safety specifications and measures given by mean-payoff automata, the optimal-synthesis problem amounts to finding a strategy in a Markov decision process (MDP) that is optimal for a long-run average reward objective, which can be done in polynomial time. For general omega-regular specifications, the solution rests on a new, polynomial-time algorithm for computing optimal strategies in MDPs with mean-payoff parity objectives. Our algorithm generates optimal strategies consisting of two memoryless strategies and a counter. This

preprint2011arXiv

Free iterative and iteration K-semialgebras

We consider algebras of rational power series over an alphabet $Σ$ with coefficients in a commutative semiring $K$ and characterize them as the free algebras in various classes of algebraic structures.

preprint2011arXiv

Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines

A weighted finite-state machine with n tapes (n-WFSM) defines a rational relation on n strings. It is a generalization of weighted acceptors (one tape) and transducers (two tapes). After recalling some basic definitions about n-ary weighted rational relations and n-WFSMs, we summarize some central operations on these relations and machines, such as join and auto-intersection. Unfortunately, due to Post's Correspondence Problem, a fully general join or auto-intersection algorithm cannot exist. We recall a restricted algorithm for a class of n-WFSMs. Through a series of practical applications, we finally investigate the augmented descriptive power of n-WFSMs and their join, compared to classical transducers and their composition. Some applications are not feasible with the latter. The series includes: the morphological analysis of Semitic languages, the preservation of intermediate results in transducer cascades, the induction of morphological rules from corpora, the alignment of lexicon entries, the automatic extraction of acronyms and their meaning from corpora, and the search for cognates in a bilingual lexicon. All described operations and applications have been implemented w

preprint2011arXiv

Computational Aspects of Asynchronous CA

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are "universal", i.e., allowing a (specific family of) ACA to simulate any TM on any input. We also consider the computational cost of such simulations.