Opening book details…
Can I read Some Logical Characterizations of the Dot-Depth Hierarchy and Applications on EtoBox?
Some Logical Characterizations of the Dot-Depth Hierarchy and Applications by F. Blanchetsadri is a Computer Science article available to read on EtoBox.
What is Some Logical Characterizations of the Dot-Depth Hierarchy and Applications about?
A logical characterization of natural subhierarchies of the dot-depth hierarchy refining a theorem of Thomas and a congruence characterization related to a version of the Ehrenfeucht-Fraïssé game generalizing a theorem of Simon are given. For a sequence \(\bar{m}=\left(m_{1}, \ldots, m_{k}\right)\) of positive integers, subclasses \(\mathscr{I}^{\prime}\left(m_{1}, \ldots, m_{k}\right)\) of languages of level \(k\) are defined. \(\mathscr{L}^{\prime}\left(m_{1}, \ldots, m_{k}\right)\) are shown to be decidable. Some properties of the characterizing congruences are studied, among them, a condition which insures \(\mathscr{L}^{\prime}\left(m_{1}, \ldots, m_{k}\right)\) to be included in \(\mathscr{L}^{\prime}\left(m_{1}^{\prime}, \ldots, m_{k}^{\prime}\right)\). A conjecture of Pin concerning tree hierarchies of monoids (the dot-depth being a particular case) is shown to be false. C 1995 Academic Press, Inc.
Who reads Some Logical Characterizations of the Dot-Depth Hierarchy and Applications?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- F. Blanchetsadri
- Publisher
- Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)
- Published
- 1995
- Language
- EN
- Field
- Computer Science (Physical Sciences)