Displaying 41 – 60 of 95

Showing per page

New applications of the wreath product of forest algebras

Howard Straubing (2013)

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

We give several new applications of the wreath product of forest algebras to the study of logics on trees. These include new simplified proofs of necessary conditions for definability in CTL and first-order logic with the ancestor relation; a sequence of identities satisfied by all forest languages definable in PDL; and new examples of languages outside CTL, along with an application to the question of what properties are definable in both CTL and LTL.

On dot-depth two

F. Blanchet-Sadri (1990)

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

On Existentially First-Order Definable Languages and Their Relation to NP

Bernd Borchert, Dietrich Kuske, Frank Stephan (2010)

RAIRO - Theoretical Informatics and Applications

Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals  iff L 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.

On the continuity set of an Omega rational function

Olivier Carton, Olivier Finkel, Pierre Simonnet (2008)

RAIRO - Theoretical Informatics and Applications

In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function f has at least one point of continuity and that its continuity set C(f) cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed. Furthermore...

On the topological complexity of infinitary rational relations

Olivier Finkel (2003)

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

We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [20].

Reconstructibility of Boolean control networks with time delays in states

Ping Sun, Lijun Zhang, Kuize Zhang (2018)

Kybernetika

This paper deals with the reconstructibility of Boolean control networks (BCNs) with time delays in states. First, a survey on the semi-tensor product, weighted pair graph, constructed forest and finite automata is given. Second, by using the weighted pair graph, constructed forest and finite automata, an algorithm is designed to judge whether a Boolean control network with time delays in states is reconstructable or not under a mild assumption. Third, an algorithm is proposed to determine the current...

Relating automata-theoretic hierarchies to complexity-theoretic hierarchies

Victor L. Selivanov (2002)

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

We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies

Victor L. Selivanov (2010)

RAIRO - Theoretical Informatics and Applications

We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

Currently displaying 41 – 60 of 95