Search results for "Automata theory"

showing 4 items of 284 documents

BALANCE PROPERTIES AND DISTRIBUTION OF SQUARES IN CIRCULAR WORDS

2010

We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalized to non periodic infinite words as well.

combinatoria delle parole parole circolari parole bilanciateCombinatoricsCombinatorics on wordsSettore INF/01 - InformaticaComputer Science (miscellaneous)Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Computer Science::Formal Languages and Automata TheoryMathematicsInternational Journal of Foundations of Computer Science
researchProduct

Varieties Generated by Certain Models of Reversible Finite Automata

2006

Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the boolean closure of the classes of languages recognized by these models.

finite monoidNested word[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]Quantum automaton0102 computer and information sciences[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Computer Science::Computational Complexityω-automatonregular language01 natural sciences[MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR]Regular languageQuantum finite automata0101 mathematicsReversible automatonMathematicsDiscrete mathematicsFinite-state machine010102 general mathematicsNonlinear Sciences::Cellular Automata and Lattice GasesMR 68Q70AutomatonClosure (mathematics)010201 computation theory & mathematicsAutomata theoryComputer Science::Formal Languages and Automata Theory
researchProduct

ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS

2012

In this paper we describe a "light" algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on real dictionaries, on biological sequences and on the sets of suffixes (resp. factors) of a set of words that shows how our automaton is near to the minimal one. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton. We moreover construct linear algorithms for the insertion and deletion of a word in a finite set, directly from the constructed automaton.

minimal automata[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Timed automatondeterministic automataBüchi automaton0102 computer and information sciences02 engineering and technology01 natural sciencesDeterministic automaton0202 electrical engineering electronic engineering information engineeringComputer Science (miscellaneous)Two-way deterministic finite automatonNondeterministic finite automatonMathematicsonline construction.Discrete mathematicsSettore INF/01 - InformaticaPowerset constructionPushdown automatonComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)010201 computation theory & mathematicsProbabilistic automaton020201 artificial intelligence & image processingFinite set of wordAlgorithmComputer Science::Formal Languages and Automata Theory
researchProduct

On Prefix Normal Words

2011

We present a new class of binary words: the prefix normal words. They are defined by the property that for any given length $k$, no factor of length $k$ has more $a$'s than the prefix of the same length. These words arise in the context of indexing for jumbled pattern matching (a.k.a. permutation matching or Parikh vector matching), where the aim is to decide whether a string has a factor with a given multiplicity of characters, i.e., with a given Parikh vector. Using prefix normal words, we give the first non-trivial characterization of binary words having the same set of Parikh vectors of factors. We prove that the language of prefix normal words is not context-free and is strictly contai…

permutation matchingcontext-free languagesSearch engine indexingpre-necklacesBinary numberParikh vectorsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Lyndon wordsnon- standard pattern matchingLyndon wordsCombinatoricsPrefixjumbled pattern matchingPattern matchingParikh vectors; pre-necklaces; Lyndon words; context-free languages; jumbled pattern matching; permutation matching; non- standard pattern matching; indexingComputer Science::Formal Languages and Automata TheoryParikh vectors pre-necklaces Lyndon words context-free languages jumbled pattern matching permutation matching non-standard pattern matching indexingMathematicsindexing
researchProduct