Hasil untuk "cs.FL"

Achim Blumensath

We study Ramsey like theorems for infinite trees and similar combinatorial tools. As an application we consider the expansion problem for tree algebras.

Teodor Knapik

A generic method for inferring a dynamical hidden Markov model from a time series is proposed. Under reasonable hypothesis, the model is updated in constant time whenever a new measurement arrives.

Dominique Perrin, Andrew Ryzhikov

We prove several results concerning finitely generated submonoids of the free monoid. These results generalize those known for free submonoids. We prove in particular that if $X=Y\circ Z$ is a composition of finite sets of words with $Y$ complete, then $d(X)\le d(Y)d(Z)$.

Vladislav Makarov

An efficient, when compared to exhaustive enumeration, algorithm for computing the number of square-free words of length $n$ over the alphabet $\{a, b, c\}$ is presented.

Jack H. Lutz, Giora Slutzki

We present a simple new method for proving that languages are not regular. We prove the correctness of the method, illustrate the ease of using the method on well-known examples of nonregular languages, and prove two additional theorems on the power and limitations of the method.

Martin Fränzle, Karin Quaas, Mahsa Shirmohammadi et al.

We give a new proof of the result of Comon and Jurski that the binary reachability relation of a timed automaton is definable in linear arithmetic.

Maria Spichkova

This paper presents a formal specification of the Controller Area Network (CAN) protocol using FocusST framework. We formally describe core components of the protocol, which provides a basis for further formal analysis using the Isabelle/HOL theorem prover.

Achim Blumensath

We introduce a class of algebras that can be used as recognisers for regular tree languages. We show that it is the only such class that forms a pseudo-variety and we prove the existence of syntactic algebras. Finally, we give a more algebraic characterisation of the algebras in our class.

Alexander Sakharov

We present a method for approximating context-free languages with one-counter automata. This approximation allows the reconstruction of parse trees of the original grammar. We identify a decidable superset of regular languages whose elements, i.e. languages, are recognized by one-counter automata.

Ines Klimann

We prove that if a group generated by a bireversible Mealy automaton contains an element of infinite order, its growth blows up and is necessarily exponential. As a direct consequence, no infinite virtually nilpotent group can be generated by a bireversible Mealy automaton.

Ines Klimann

We prove that if the group generated by a Mealy automaton acts level-transitively on a regular rooted tree, then the semigroup generated by the dual automaton has exponential growth, hence giving a decision procedure of exponential growth for a restricted family of automaton semigroups.

Jeffrey Shallit

We determine the minimum possible critical exponent for all palindromes over finite alphabets.

Jochen Burghardt

We prove the NP-hardness of the problem whether a given word can be derived from a given regular grammar without repeated occurrence of any nonterminal.

Joost Engelfriet

Lecture notes on tree language theory, in particular recognizable tree languages and finite state tree transformations.

Vojtěch Vorel

First, we show that universality and other properties of general jumping finite automata are undecidable, which answers a question asked by Meduna and Zemek in 2012. Second, we close the study raised by Černo and Mráz in 2010 by proving that clearing restarting automata using contexts of size two can accept binary non-context-free languages.

Takayuki Kuriyama

We generalized the class of $k,l$-substitutable languages (Yoshinala, 2008). Each language in the generalized class is closed under a good substitutability. The substitutability is defined by a recognizable equivalence relation. We show the convergence of our generalized learning algorithm. The size of the characteristic sample is smaller than Yoshinaka's.

Vladimir V. Gusev

We study the problem of synchronization of automata with random inputs. We present a series of automata such that the expected number of steps until synchronization is exponential in the number of states. At the same time, we show that the expected number of letters to synchronize any pair of the famous Cerny automata is at most cubic in the number of states.

Maurice Margenstern

In this paper we give three examples of expending patterns defined by hyperbolic cellular automata whose growth seems to be very similar to the growth of colonies of bacteria.

Franck Cassez

In this paper we extend the work on \emph{dynamic ob\-servers} for fault diagnosis to timed automata. We study sensor minimization problems with static observers and then address the problem of computing the most permissive dynamic observer for a system given by a timed automaton.

M. V. Berlinkov

We prove that, unless $\mathrm{P}=\mathrm{NP}$, no polynomial algorithm can approximate the minimum length of \sws for a given \san within a constant factor.