All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 4

Displaying 61 – 79 of 79

Showing per page

Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)

RAIRO - Theoretical Informatics and Applications

An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet can be interpreted...

Construction of a Deterministic ω-Automaton Using Derivatives

Roman R. Redziejowski (2010)

RAIRO - Theoretical Informatics and Applications

A deterministic automaton recognizing a given ω-regular language is constructed from an ω-regular expression with the help of derivatives. The construction is related to Safra's algorithm, in about the same way as the classical derivative method is related to the subset construction.

Construction of tree automata from regular expressions

Dietrich Kuske, Ingmar Meinecke (2011)

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

Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov's partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud and Ziadi from words...

Construction of tree automata from regular expressions

Dietrich Kuske, Ingmar Meinecke (2011)

RAIRO - Theoretical Informatics and Applications

Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov's partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud and Ziadi...

Conversion of regular expressions into realtime automata

Viliam Geffert, L'ubomíra Ištoňová (2006)

RAIRO - Theoretical Informatics and Applications

We consider conversions of regular expressions into k-realtime finite state automata, i.e., automata in which the number of consecutive uses of ε-transitions, along any computation path, is bounded by a fixed constant k. For 2-realtime automata, i.e., for automata that cannot change the state, without reading an input symbol, more than two times in a row, we show that the conversion of a regular expression into such an automaton produces only O(n) states, O(nlogn) ε-transitions, and O(n) alphabet-transitions....

Conway's Games and Some of their Basic Properties

Robin Nittka (2011)

Formalized Mathematics

We formulate a few basic concepts of J. H. Conway's theory of games based on his book [6]. This is a first step towards formalizing Conway's theory of numbers into Mizar, which is an approach to proving the existence of a FIELD (i.e., a proper class that satisfies the axioms of a real-closed field) that includes the reals and ordinals, thus providing a uniform, independent and simple approach to these two constructions that does not go via the rational numbers and hence does for example not need...

Corrigendum

Joffroy Beauquier (1979)

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

Corrigendum to our paper: How Expressions Can Code for Automata

Sylvain Lombardy, Jacques Sakarovitch (2010)

RAIRO - Theoretical Informatics and Applications

In a previous paper, we have described the construction of an automaton from a rational expression which has the property that the automaton built from an expression which is itself computed from a co-deterministic automaton by the state elimination method is co-deterministic. It turned out that the definition on which the construction is based was inappropriate, and thus the proof of the property was flawed. We give here the correct definition of the broken derived terms of an...

Currently displaying 61 – 79 of 79

Previous Page 4