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 78

Showing per page

Finding H-partitions efficiently

Simone Dantas, Celina M.H. de Figueiredo, Sylvain Gravier, Sulamita Klein (2010)

RAIRO - Theoretical Informatics and Applications

We study the concept of an H-partition of the vertex set of a graph G, which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph H, with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, 4-part, external...

Finite automata and algebraic extensions of function fields

Kiran S. Kedlaya (2006)

Journal de Théorie des Nombres de Bordeaux

We give an automata-theoretic description of the algebraic closure of the rational function field 𝔽 q ( t ) over a finite field 𝔽 q , generalizing a result of Christol. The description occurs within the Hahn-Mal’cev-Neumann field of “generalized power series” over 𝔽 q . In passing, we obtain a characterization of well-ordered sets of rational numbers whose base p expansions are generated by a finite automaton, and exhibit some techniques for computing in the algebraic closure; these include an adaptation to positive...

Finite models and finitely many variables

Anuj Dawar (1999)

Banach Center Publications

This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.

Fixed points of endomorphisms of certain free products

Pedro V. Silva (2012)

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

The fixed point submonoid of an endomorphism of a free product of a free monoid and cyclic groups is proved to be rational using automata-theoretic techniques. Maslakova’s result on the computability of the fixed point subgroup of a free group automorphism is generalized to endomorphisms of free products of a free monoid and a free group which are automorphisms of the maximal subgroup.

Fixed points of endomorphisms of certain free products

Pedro V. Silva (2012)

RAIRO - Theoretical Informatics and Applications

The fixed point submonoid of an endomorphism of a free product of a free monoid and cyclic groups is proved to be rational using automata-theoretic techniques. Maslakova’s result on the computability of the fixed point subgroup of a free group automorphism is generalized to endomorphisms of free products of a free monoid and a free group which are automorphisms of the maximal subgroup.

Fixpoint alternation: arithmetic, transition systems, and the binary tree

J. C. Bradfield (2010)

RAIRO - Theoretical Informatics and Applications

We provide an elementary proof of the fixpoint alternation hierarchy in arithmetic, which in turn allows us to simplify the proof of the modal mu-calculus alternation hierarchy. We further show that the alternation hierarchy on the binary tree is strict, resolving a problem of Niwiński.

Currently displaying 21 – 40 of 78