Search results for "Formal language"
showing 10 items of 357 documents
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
2008
We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumaki on the cha- racterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators, we prove that if H and K are two finitely generated submonoids generated by prefix sets such that the product automaton associated to H ∩ K has a given special property then �(H ∩ K) ≤ �(H)�(K…
Sobriety and spatiality in categories of lattice-valued algebras
2012
The paper provides an analogue of the famous equivalence between the categories of sober topological spaces and spatial locales for the framework of (L,M)-fuzzy topology of Kubiak and Sostak (and partly to that of Guido). To be more general, we replace locales with localic lattice-valued algebras in the sense of Di Nola and Gerla and use the respective generalized topological setting. As a result, it appears that the shift from crisp algebras to lattice-valued algebras weakens (resp. strengthens) considerably the classical (including the point-set lattice-theoretic setting of Rodabaugh) notion of sobriety (resp. spatiality).
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.
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.
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.