Search results for " Automata"
showing 10 items of 436 documents
Symbolic Dynamics of Geodesic Flows on Trees
2019
In this chapter, we give a coding of the discrete-time geodesic ow on the nonwandering sets of quotients of locally finite simplicial trees X without terminal vertices by nonelementary discrete subgroups of Aut(X) by a subshift of finite type on a countable alphabet.
Running time to recognize nonregular languages by 2-way probabilistic automata
1991
R. Freivalds proved that the language {0m1m} can be recognized by 2-way probabilistic finite automata (2pfa) with arbitrarily high probability 1-ɛ. A.G.Greenberg and A.Weiss proved that no 2pfa can recognize this language in expected time \(T(n) = c^\circ{(n)}\). For arbitrary languages C.Dwork and L.Stockmeyer showed somewhat less: if a language L is recognized by a 2pfa in expected time \(T(n) = c^{n^\circ{(1)} }\), then L is regular. First, we improve this theorem replacing the expected time by the time with probability 1-ɛ. On the other hand, time bound by C.Dwork and L.Stockmeyer cannot be improved: for arbitrary k≥2 we exhibit a specific nonregular language that can be recognized by 2…
On bijections vs. unary functions
1996
A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses of Binary NP were considered, in which the second order quantifiers range only over certain classes of relations. It was shown that many of these subclasses coincide and that all of them can be ordered in a three-level linear hierarchy, the levels of which are represented by bijections, successor relations and unary functions respectively.
Tally languages accepted by alternating multitape finite automata
1997
We consider k-tape 1-way alternating finite automata (k-tape lafa). We say that an alternating automaton accepts a language L\(\subseteq\)(Σ*)k with f(n)-bounded maximal (respectively, minimal) leaf-size if arbitrary (respectively, at least one) accepting tree for any (w1, w2,..., wk) ∈ L has no more than $$f\mathop {(\max }\limits_{1 \leqslant i \leqslant k} \left| {w_i } \right|)$$ leaves. The main results of the paper are the following. If k-tape lafa accepts language L over one-letter alphabet with o(log n)-bounded maximal leaf-size or o(log log n)-bounded minimal leaf-size then the language L is semilinear. Moreover, if a language L is accepted with o(log log(n))-bounded minimal (respe…
K4-free Graphs as a Free Algebra
2017
International audience; Graphs of treewidth at most two are the ones excluding the clique with four vertices (K4) as a minor, or equivalently, the graphs whose biconnected components are series-parallel. We turn those graphs into a finitely presented free algebra, answering positively a question by Courcelle and Engelfriet, in the case of treewidth two. First we propose a syntax for denoting these graphs: in addition to parallel composition and series composition, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equational presentation and we prove it complete: two terms from the syntax are congruent if and only if they …
On the Online Classification of Data Streams Using Weak Estimators
2016
In this paper, we propose a novel online classifier for complex data streams which are generated from non-stationary stochastic properties. Instead of using a single training model and counters to keep important data statistics, the introduced online classifier scheme provides a real-time self-adjusting learning model. The learning model utilizes the multiplication-based update algorithm of the Stochastic Learning Weak Estimator (SLWE) at each time instant as a new labeled instance arrives. In this way, the data statistics are updated every time a new element is inserted, without requiring that we have to rebuild its model when changes occur in the data distributions. Finally, and most impo…
Codification schemes and finite automata
2000
This paper is a note on how Information Theory and Codification Theory are helpful in the computational design both of communication protocols and strategy sets in the framework of finitely repeated games played by boundedly rational agents. More precisely, we show the usefulness of both theories to improve the existing automata bounds of Neyman¿s (1998) work on finitely repeated games played by finite automata.
Linear-size suffix tries
2016
Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and lin…
Learning Automata-based Misinformation Mitigation via Hawkes Processes
2021
AbstractMitigating misinformation on social media is an unresolved challenge, particularly because of the complexity of information dissemination. To this end, Multivariate Hawkes Processes (MHP) have become a fundamental tool because they model social network dynamics, which facilitates execution and evaluation of mitigation policies. In this paper, we propose a novel light-weight intervention-based misinformation mitigation framework using decentralized Learning Automata (LA) to control the MHP. Each automaton is associated with a single user and learns to what degree that user should be involved in the mitigation strategy by interacting with a corresponding MHP, and performing a joint ra…
A Fast Algorithm Finding the Shortest Reset Words
2013
In this paper we present a new fast algorithm for finding minimal reset words for finite synchronizing automata, which is a problem appearing in many practical applications. The problem is known to be computationally hard, so our algorithm is exponential in the worst case, but it is faster than the algorithms used so far and it performs well on average. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare subsets. Also a number of heuristics are applied. We give both theoretical and practical arguments showing that the effective branching factor is considerably reduced. As a practical test we perform an experimental study of the length of the shortest …