Displaying similar documents to “On the classes of languages accepted by limited context restarting automata”

On biautomata

Ondřej Klíma, Libor Polák (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language its canonical biautomaton. This structure plays, among all biautomata recognizing the language , the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language . We expect that from the graph structure of this automaton one could decide the membership of a given language...

Distance desert automata and the star height problem

Daniel Kirsten (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 2 space whether the language accepted by an -state non-deterministic automaton is of a star height less than a given integer (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity...

On biautomata

Ondřej Klíma, Libor Polák (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language its canonical biautomaton. This structure plays, among all biautomata recognizing the language , the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language . We expect that from the graph structure of this automaton one could decide the membership of a given language...

On differentiation functions, structure functions, and related languages of context-free grammars

Jürgen Dassow, Victor Mitrana, Gheorghe Păun, Ralf Stiebe (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or -narrow) iff its differentiation function is bounded by a constant (by ). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability...

k-counting automata

Joël Allred, Ulrich Ultes-Nitsche (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

In this paper, we define -counting automata as recognizers for -languages, languages of infinite words. We prove that the class of -languages they recognize is a proper extension of the -regular languages. In addition we prove that languages recognized by -counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for -counting automata. However, we conjecture strongly that it is decidable and give formal reasons why we believe...

Hyper-minimizing minimized deterministic finite state automata

Andrew Badr, Viliam Geffert, Ian Shipman (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications, the construction...