Search results for "Crete"
showing 10 items of 2495 documents
Testing Grammars for Parsability
1990
In the preceding chapters we have studied in detail the major methods of deterministic context-free parsing: strong LL(k) parsing (Chapter 5), simple precedence parsing (Chapter 5), canonical LR(k) parsing, LALR(k) parsing, and SLR(k) parsing (Chapters 6 and 7), and canonical LL(k) parsing (Chapter 8). Each of these methods induces a class of grammars that are “parsable” using that method, that is, a class of grammars for which a deterministic parser employing that method can be constructed. For example, the LL(k) grammars constitute the class of grammars parsable by the LL(k) parsing method. By definition, a context-free grammar is an LL(k) grammar if and only if its canonical LL(k) parser…
On Formations of Finite Groups with the Wielandt Property for Residuals
2001
Abstract Given two subgroups U, V of a finite group which are subnormal subgroups of their join 〈U, V〉 and a formation F , in general it is not true that 〈U, V〉 F = 〈U F , V F 〉. A formation is said to have the Wielandt property if this equality holds universally. A formation with the Wielandt property must be a Fitting class. Wielandt proved that the most usual Fitting formations (e.g., nilpotent groups and π-groups) have the Wielandt property. At present, neither a general satisfactory result on the universal validity of the Wielandt property nor a counterexample is known. In this paper a criterion for a Fitting formation to have the Wielandt property is given. As an application, it is p…
On point-irreducible projective lattice geometries
1994
Within the conceptual frame of projective lattice geometry (as introduced in [5]) we are considering the class of all point-irreducible geometries. In the algebraic context these geometries are closely connected with unitary modules over local rings. Besides several synthetic investigations we obtain a lattice-geometric characterization of free left modules over right chain rings which allows a purely lattice-theoretic version in the Artinian case.
Analytic Extension of Non Quasi - Analytic Whitney Jets of Beurling Type
1998
Let (Mr)r∈ℕ0 be a logarithmically convex sequence of positive numbers which verifies M0 = 1 as well as Mr ≥ 1 for every r ∈ ℕ and defines a non quasi - analytic class. Let moreover F be a closed proper subset of ℝn. Then for every function f on ℝn belonging to the non quasi - analytic (Mr)-class of Beurling type, there is an element g of the same class which is analytic on ℝ,nF and such that Dαf(x) = Dαg(x) for every α ∈ ℕn0 and x ∈ F.
On a class of languages recognizable by probabilistic reversible decide-and-halt automata
2009
AbstractWe analyze the properties of probabilistic reversible decide-and-halt automata (DH-PRA) and show that there is a strong relationship between DH-PRA and 1-way quantum automata. We show that a general class of regular languages is not recognizable by DH-PRA by proving that two “forbidden” constructions in minimal deterministic automata correspond to languages not recognizable by DH-PRA. The shown class is identical to a class known to be not recognizable by 1-way quantum automata. We also prove that the class of languages recognizable by DH-PRA is not closed under union and other non-trivial Boolean operations.
On the Hierarchy Classes of Finite Ultrametric Automata
2015
This paper explores the language classes that arise with respect to the head count of a finite ultrametric automaton. First we prove that in the one-way setting there is a language that can be recognized by a one-head ultrametric finite automaton and cannot be recognized by any k-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite k-head automata is a proper subclass of the class of languages recognized by (k + 1)-head automata. Ultrametric finite automata are similar to probabilistic and quantum automata and have only just recently been introduced by Freivalds. We introduce ultrametric Turing machines an…
Periodic Groups Covered by Transitive Subgroups of Finitary Permutations or by Irreducible Subgroups of Finitary Transformations
1999
Let X be either the class of all transitive groups of finitary permutations, or the class of all periodic irreducible finitary linear groups. We show that almost primitive X-groups are countably recognizable, while totally imprimitive X-groups are in general not countably recognizable. In addition we derive a structure theorem for groups all of whose countable subsets are contained in totally imprimitive X-subgroups. It turns out that totally imprimitive p-groups in the class X are countably recognizable.
Querying the Guarded Fragment with Transitivity
2016
We study the problem of answering a union of Boolean conjunctive queries q against a database Δ, and a logical theory φ which falls in the guarded fragment with transitive guards (GF + TG). We trace the frontier between decidability and undecidability of the problem under consideration. Surprisingly, we show that query answering under GF2 + TG, i.e., the two-variable fragment of GF + TG, is already undecidable (even without equality), whereas its monadic fragment is decidable; in fact, it is 2exptime-complete in combined complexity and coNP-complete in data complexity. We also show that for a restricted class of queries, query answering under GF+TG is decidable. © 2013 Springer-Verlag.
Varieties of Codes and Kraft Inequality
2005
Decipherability conditions for codes are investigated by using the approach of Guzman, who introduced in [7] the notion of variety of codes and established a connection between classes of codes and varieties of monoids. The class of Uniquely Decipherable (UD) codes is a special case of variety of codes, corresponding to the variety of all monoids. It is well known that the Kraft inequality is a necessary condition for UD codes, but it is not sufficient, in the sense that there exist codes that are not UD and that satisfy the Kraft inequality. The main result of the present paper states that, given a variety $\mathcal{V}$ of codes, if all the elements of $\mathcal{V}$ satisfy the Kraft inequ…
Mappings of finite distortion: The zero set of the Jacobian
2003
This paper is part of our program to establish the fundamentals of the theory of mappings of finite distortion [6], [1], [8], [13], [14], [7] which form a natural generalization of the class of mappings of bounded distortion, also called quasiregular mappings. Let us begin with the definition. We assume that Ω ⊂ Rn is a connected open set. We say that a mapping f : Ω → Rn has finite distortion if: