Search results for "Büchi automaton"

showing 7 items of 17 documents

Minimal Büchi Automata for Certain Classes of LTL Formulas

2009

In this paper we calculate the minimal number of states of Buchi automata which encode some classes of linear temporal logic (LTL) formulas that are frequently used in model checking. Our results may be used for verification of the quality of algorithms which automatically translate LTL formulas into Buchi automata and for improving the quality and speed of such translators. In the last section of this paper we compare our lower-bound estimations to Buchi automata generated by two currently used translators: LTL2BA and SPOT.

Model checkingTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTheoretical computer scienceLinear temporal logicComputer scienceComputer Science::Logic in Computer ScienceBüchi automatonAutomata theoryTemporal logicComputer Science::Formal Languages and Automata Theory2009 Fourth International Conference on Dependability of Computer Systems
researchProduct

Special factors and the combinatorics of suffix and factor automata

2011

AbstractThe suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.

Special factorGeneral Computer ScienceSpecial factorsFactor automatonBüchi automatonω-automatonTheoretical Computer ScienceCombinatoricsDeterministic automatonTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Data Structures and AlgorithmsCombinatorics on wordStandard Sturmian wordsMathematicsDiscrete mathematicsCombinatorics on wordsDAWGPushdown automatonComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nonlinear Sciences::Cellular Automata and Lattice GasesSuffix automatonProbabilistic automatonSuffix automatonComputer Science::Formal Languages and Automata TheoryComputer Science(all)Theoretical Computer Science
researchProduct

Quantum versus Probabilistic One-Way Finite Automata with Counter

2001

The paper adds the one-counter one-way finite automaton [6] to the list of classical computing devices having quantum counterparts more powerful in some cases. Specifically, two languages are considered, the first is not recognizable by deterministic one-counter one-way finite automata, the second is not recognizable with bounded error by probabilistic one-counter one-way finite automata, but each recognizable with bounded error by a quantum one-counter one-way finite automaton. This result contrasts the case of one-way finite automata without counter, where it is known [5] that the quantum device is actually less powerful than its classical counterpart.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordComputer scienceTimed automatonBüchi automatonω-automatonNondeterministic finite automaton with ε-movesTuring machinesymbols.namesakeDFA minimizationDeterministic automatonContinuous spatial automatonQuantum finite automataDeterministic system (philosophy)Two-way deterministic finite automatonNondeterministic finite automatonDiscrete mathematicsFinite-state machineQuantum dot cellular automatonNonlinear Sciences::Cellular Automata and Lattice GasesMobile automatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonProbabilistic automatonsymbolsAutomata theoryComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton
researchProduct

Automata and forbidden words

1998

Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Büchi automaton0102 computer and information sciences02 engineering and technologyω-automaton01 natural sciencesTheoretical Computer ScienceCombinatoricsDeterministic automaton0202 electrical engineering electronic engineering information engineeringTwo-way deterministic finite automatonNondeterministic finite automatonMathematicsPowerset constructionLevenshtein automaton020206 networking & telecommunicationsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nonlinear Sciences::Cellular Automata and Lattice GasesComputer Science ApplicationsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematicsSignal ProcessingProbabilistic automatonComputer Science::Programming LanguagesComputer Science::Formal Languages and Automata TheoryInformation Systems
researchProduct

Minimal forbidden words and factor automata

1998

International audience; Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is eff ective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESfailure functionfactor code[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Büchi automatonComputerApplications_COMPUTERSINOTHERSYSTEMS[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciencesavoiding a wordω-automaton01 natural sciencesfactorial languageReversible cellular automatonCombinatoricsDeterministic automatonanti-factorial languageNondeterministic finite automaton0101 mathematicsMathematicsfactor automatonPowerset constructionLevenshtein automaton010102 general mathematicsforbidden wordComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)16. Peace & justiceNonlinear Sciences::Cellular Automata and Lattice GasesTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematicsProbabilistic automatonPhysics::Accelerator PhysicsComputer Science::Programming LanguagesHigh Energy Physics::ExperimentComputer Science::Formal Languages and Automata Theory
researchProduct

On the suffix automaton with mismatches

2007

International audience; In this paper we focus on the construction of the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of S_k in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.

approximate string matchingFibonacci numberlanguages with mismatches[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Generalized suffix treeBüchi automatonComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)0102 computer and information sciences02 engineering and technology01 natural sciencesCombinatoricsPrefixCombinatorics on wordsDeterministic finite automaton010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringSuffix automaton020201 artificial intelligence & image processingsuffix automatacombinatorics on wordsComputer Science::Data Structures and Algorithmscombinatorics on words suffix automata languages with mismatches approximate string matchingWord (computer architecture)Computer Science::Formal Languages and Automata TheoryMathematics
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