Search results for "formal"
showing 10 items of 1654 documents
Automata and differentiable words
2011
We exhibit the construction of a deterministic automaton that, given k > 0, recognizes the (regular) language of k-differentiable words. Our approach follows a scheme of Crochemore et al. based on minimal forbidden words. We extend this construction to the case of C\infinity-words, i.e., words differentiable arbitrary many times. We thus obtain an infinite automaton for representing the set of C\infinity-words. We derive a classification of C\infinity-words induced by the structure of the automaton. Then, we introduce a new framework for dealing with \infinity-words, based on a three letter alphabet. This allows us to define a compacted version of the automaton, that we use to prove that ev…
Quantum Finite Automata and Logics
2006
The connection between measure once quantum finite automata (MO-QFA) and logic is studied in this paper. The language class recognized by MO-QFA is compared to languages described by the first order logics and modular logics. And the equivalence between languages accepted by MO-QFA and languages described by formulas using Lindstrom quantifier is shown.
Heyting-valued interpretations for Constructive Set Theory
2006
AbstractWe define and investigate Heyting-valued interpretations for Constructive Zermelo–Frankel set theory (CZF). These interpretations provide models for CZF that are analogous to Boolean-valued models for ZF and to Heyting-valued models for IZF. Heyting-valued interpretations are defined here using set-generated frames and formal topologies. As applications of Heyting-valued interpretations, we present a relative consistency result and an independence proof.
Logics with counting and equivalence
2014
We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NEXPTIME-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.
The Phagocyte Lattice of Dyck Words
2006
We introduce a new lattice structure on Dyck words. We exhibit efficient algorithms to compute meets and joins of Dyck words.
Ordering and Convex Polyominoes
2005
We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes. In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set P is a L-convex polyomino if and only if all the elements Q≼P are polyominoes. In the seco…
Reconstruction of L-convex Polyominoes.
2003
Abstract We introduce the family of L-convex polyominoes, a subset of convex polyominoes whose elements satisfy a special convexity property. We develop an algorithm that reconstructs an L-convex polyomino from the set of its maximal L-polyominoes.
Rearrangement and convergence in spaces of measurable functions
2007
We prove that the convergence of a sequence of functions in the space of measurable functions, with respect to the topology of convergence in measure, implies the convergence -almost everywhere ( denotes the Lebesgue measure) of the sequence of rearrangements. We obtain nonexpansivity of rearrangement on the space , and also on Orlicz spaces with respect to a finitely additive extended real-valued set function. In the space and in the space , of finite elements of an Orlicz space of a -additive set function, we introduce some parameters which estimate the Hausdorff measure of noncompactness. We obtain some relations involving these parameters when passing from a bounded set of , or , to th…
Optimal paths in weighted timed automata
2004
AbstractWe consider the optimal-reachability problem for a timed automaton with respect to a linear cost function which results in a weighted timed automaton. Our solution to this optimization problem consists of reducing it to computing (parametric) shortest paths in a finite weighted directed graph. We call this graph a parametric sub-region graph. It refines the region graph, a standard tool for the analysis of timed automata, by adding the information which is relevant to solving the optimal-reachability problem. We present an algorithm to solve the optimal-reachability problem for weighted timed automata that takes time exponential in O(n(|δ(A)|+|wmax|)), where n is the number of clock…
Compactness of time-frequency localization operators on L2(Rd)
2006
Abstract In this paper, we consider localization operators on L 2 ( R d ) defined by symbols in a subclass of the modulation space M ∞ ( R 2 d ) . We show that these operators are compact and that this subclass is “optimal” for compactness.