A fast algorithm to decide on the equivalence of stateless DPDA
A Fast Las Vegas Algorithm for Triangulating a Simple Polygon.
A finite axiomatization of nondeterministic regular expressions
A Finite Axiomatization of Nondeterministic Regular Expressions
An alternative (tree-based) semantics for a class of regular expressions is proposed that assigns a central rôle to the + operator and thus to nondeterminism and nondeterministic choice. For the new semantics a consistent and complete axiomatization is obtained from the original axiomatization of regular expressions by Salomaa and by Kozen by dropping the idempotence law for + and the distribution law of • over +.
A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs
We characterize the class [...] L32 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 in the class of threshold graphs, where n is the number of vertices of a tested graph.
A finiteness property and an automatic structure for Coxeter groups.
A fully equational proof of Parikh’s theorem
We show that the validity of Parikh’s theorem for context-free languages depends only on a few equational properties of least pre-fixed points. Moreover, we exhibit an infinite basis of -term equations of continuous commutative idempotent semirings.
A Fully Equational Proof of Parikh's Theorem
We show that the validity of Parikh's theorem for context-free languages depends only on a few equational properties of least pre-fixed points. Moreover, we exhibit an infinite basis of μ-term equations of continuous commutative idempotent semirings.
A fuzzy computational model implementation
A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II
The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed ω-semigroups of width 2 and height ωω. 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 ω-semigroups allowing to compute their precise Wagner degrees. The Wagner degree of any ω-rational language can therefore be computed...
A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I
The algebraic study of formal languages shows that ω-rational sets correspond precisely to the ω-languages recognizable by finite ω-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the ω-rational language to the ω-semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on...
A general framework for the derivation of regular expressions
The aim of this paper is to design a theoretical framework that allows us to perform the computation of regular expression derivatives through a space of generic structures. Thanks to this formalism, the main properties of regular expression derivation, such as the finiteness of the set of derivatives, need only be stated and proved one time, at the top level. Moreover, it is shown how to construct an alternating automaton associated with the derivation of a regular expression in this general framework....
A generalization of configurations in the sense of Gladkij
A generalization of the propositional calculus for purposes of the theory of logical nets with probabilistic elements
A generalization of traces
A generalized minimal realization theory of machines in a category.
This paper presents a generalized minimal realization theory of machines in a category which contains the Kleiski case. The minimal realization is the cheapest realization for a given cost functor. The final reachable realization of Arbib and Manes ([5]) and the minimal state approach for nondeterministic machines are included here.
A Generalized Model of PAC Learning and its Applicability
We combine a new data model, where the random classification is subjected to rather weak restrictions which in turn are based on the Mammen−Tsybakov [E. Mammen and A.B. Tsybakov, Ann. Statis. 27 (1999) 1808–1829; A.B. Tsybakov, Ann. Statis. 32 (2004) 135–166.] small margin conditions, and the statistical query (SQ) model due to Kearns [M.J. Kearns, J. ACM 45 (1998) 983–1006] to what we refer to as PAC + SQ model. We generalize the class conditional constant noise (CCCN) model introduced by Decatur...
A Geometric Inequality and the Complexity of Computing Volume.
A geometrical method in combinatorial complexity
A lower bound for the number of comparisons is obtained, required by a computational problem of classification of an arbitrarily chosen point of the Euclidean space with respect to a given finite family of polyhedral (non-convex, in general) sets, covering the space. This lower bound depends, roughly speaking, on the minimum number of convex parts, into which one can decompose these polyhedral sets. The lower bound is then applied to the knapsack problem.
A grammatical inference for -finite languages