Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1175.03022
Cabessa, Jérémie; Duparc, Jacques
A game theoretical approach to the algebraic counterpart of the Wagner hierarchy. II. (English)
[J] Theor. Inform. Appl. 43, No. 3, 463-515 (2009). ISSN 0988-3754; ISSN 1290-385X/e

Summary: The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed $\omega$-semigroups of width 2 and height $\omega^\omega$. This paper completes the description of this algebraic hierarchy. We first give a purely algebraic decidability procedure of this partial ordering by introducing a graph representation of finite pointed $\omega$-semigroups allowing to compute their precise Wagner degrees. The Wagner degree of any $\omega$-rational language can therefore be computed directly on its syntactic image. We then show how to build a finite pointed $\omega$-semigroup of any given Wagner degree. We finally describe the algebraic invariants characterizing every degree of this hierarchy. For Part I see ibid. 43, No.~3, 443--461 (2009; Zbl 1175.03021).

MSC 2000:: *03D05 Automata theory in connection with logical questions
03E15 Descriptive set theory (logic)
20M35 Semigroups in automata theory, linguistics, etc.
68Q70 Algebraic theory of automata
91A65 Hierarchical games

Keywords: $\omega$-automata; $\omega$-rational languages; $\omega$-semigroups; infinite games; hierarchical games; Wadge game; Wadge hierarchy; Wagner hierarchy

Citations: Zbl 1175.03021

Cited in: Zbl 1175.03021

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]