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 2 Next

Displaying 21 – 40 of 79

Showing per page

Closure properties of hyper-minimized automata

Andrzej Szepietowski (2011)

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

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton A is hyper-minimized if no automaton with fewer states is almost equivalent to A. A regular language L is canonical if the minimal automaton accepting L is hyper-minimized. The asymptotic state complexity s∗(L) of a regular language L is the number of states of a hyper-minimized automaton for a language finitely different from L. In this paper we show that: (1) the class...

Closure properties of hyper-minimized automata

Andrzej Szepietowski (2012)

RAIRO - Theoretical Informatics and Applications

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton A is hyper-minimized if no automaton with fewer states is almost equivalent to A. A regular language L is canonical if the minimal automaton accepting L is hyper-minimized. The asymptotic state complexity s∗(L) of a regular language L is the number of states of a hyper-minimized automaton for a language ...

Closure under union and composition of iterated rational transductions

D. Simplot, A. Terlutte (2010)

RAIRO - Theoretical Informatics and Applications

We proceed our work on iterated transductions by studying the closure under union and composition of some classes of iterated functions. We analyze this closure for the classes of length-preserving rational functions, length-preserving subsequential functions and length-preserving sequential functions with terminal states. All the classes we obtain are equal. We also study the connection with deterministic context-sensitive languages.

Codes et motifs

Bodonirina Ratoandromanana (1989)

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

Cohesiveness in promise problems

Ulrike Brandt, Hermann K.-G. Walter (2013)

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

Promise problems have been introduced in 1985 by S. Even e.a. as a generalization of decision problems. Using a very general approach we study solvability and unsolvability conditions for promise problems of set and language families. We show, that cores of unsolvability are completely determined by partitions of cohesive sets. We prove the existence of cores in unsolvable promise problems assuming certain closure properties for the given set family. Connections to immune sets and complexity cores...

Comparing Complexity Functions of a Language and Its Extendable Part

Arseny M. Shur (2008)

RAIRO - Theoretical Informatics and Applications

Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2004)

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

We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2010)

RAIRO - Theoretical Informatics and Applications

We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog.
Succinctness...

Compatibility relations on codes and free monoids

Tomi Kärki (2008)

RAIRO - Theoretical Informatics and Applications

A compatibility relation on letters induces a reflexive and symmetric relation on words of equal length. We consider these word relations with respect to the theory of variable length codes and free monoids. We define an (R,S)-code and an (R,S)-free monoid for arbitrary word relations R and S. Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are (R,S)-codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations....

Currently displaying 21 – 40 of 79