Displaying similar documents to “On differentiation functions, structure functions, and related languages of context-free grammars”

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...

On the classes of languages accepted by limited context restarting automata

Friedrich Otto, Peter Černo, František Mráz (2014)

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

Similarity:

In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word is accepted by such an automaton if, starting from the initial configuration that corresponds to input , the word is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context...

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 Existentially First-Order Definable Languages and Their Relation to NP

Bernd Borchert, Dietrich Kuske, Frank Stephan (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language : the unbalanced polynomial-time leaf language class determined by equals  iff is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.

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...

-counting automata

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

RAIRO - Theoretical Informatics and 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...

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...