Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
6,173
result(s) for
"Automata theory"
Sort by:
On Polynomial Recursive Sequences
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is bn = n!. Our main result is that the sequence un = nn is not polynomial recursive.
Journal Article
Abelian networks IV. Dynamics of nonhalting networks
An abelian network is a collection of communicating automata whose state transitions and message passing each satisfy a local
commutativity condition. This paper is a continuation of the abelian networks series of Bond and Levine (2016), for which we extend the
theory of abelian networks that halt on all inputs to networks that can run forever. A nonhalting abelian network can be realized as a
discrete dynamical system in many different ways, depending on the update order. We show that certain features of the dynamics, such as
minimal period length, have intrinsic definitions that do not require specifying an update order.
We give an intrinsic definition
of the
This perspective leads to
new results even in the classical case of sinkless rotor networks (deterministic analogues of random walks). In Holroyd et. al (2008) it
was shown that the recurrent configurations of a sinkless rotor network with just one chip are precisely the unicycles (spanning
subgraphs with a unique oriented cycle, with the chip on the cycle). We generalize this result to abelian mobile agent networks with any
number of chips. We give formulas for generating series such as
eBook
On the Ideal Arithmetic Autocorrelation of Binary FCSR Sequences
We study the arithmetic autocorrelation of binary sequences generated by a feedback with carry shift register. We find necessary and sufficient conditions for the existence of families of such sequences with ideal arithmetic autocorrelation for arbitrary connection integer . Under these conditions, any pair of cyclically different sequences with connection integer also has ideal arithmetic crosscorrelation.
Journal Article
ARGo: augmented reality-based mobile Go stone collision game
In this study, we present a mobile Go stone collision game based on augmented reality, which we call ARGo, inspired by the traditional Korean board game, Alkkagi. ARGo aims to resolve two main issues: (1) the portability and space constraints of the original Alkkagi and (2) the limited sense of reality due to the touchscreen-based interface of the existing mobile Alkkagi games. To improve a sense of the reality of the game, ARGo provides a gameplay interface similar to the original Alkkagi by recognizing the user‘s hand motion based on AR. Additionally, it provides a customization mechanism for each user to improve the recognition of the hand motion and the strength of the attack considering each user‘s characteristics. Finally, we make the following three main contributions. First, we employ the automata theory to design the game and collision scenarios between stones. Consequently, we can clearly define the complicated states incurred by AR-based motion recognition and collisions between virtual objects. Second, we propose a collision equation based on Continuous Collision Detection tailored to ARGo, i.e., Go stones and their collisions. Through experimental studies, we demonstrate that the collision equation enables the simulation of the exact collision effects. Third, through user experience studies, we verify the effectiveness of ARGo by showing the effects of the functions implemented in ARGo and its superiority over the existing mobile game Alkkagi Mania.
Journal Article
Efficient Construction of the Equation Automaton
This paper describes a fast algorithm for constructing directly the equation automaton from the well-known Thompson automaton associated with a regular expression. Allauzen and Mohri have presented a unified construction of small automata and gave a construction of the equation automaton with time and space complexity in O(mlogm+m2), where m denotes the number of Thompson automaton transitions. It is based on two classical automata operations, namely epsilon-removal and Hopcroft’s algorithm for deterministic Finite Automata (DFA) minimization. Using the notion of c-continuation, Ziadi et al. presented a fast computation of the equation automaton in O(m2) time complexity. In this paper, we design an output-sensitive algorithm combining advantages of the previous algorithms and show that its computational complexity can be reduced to O(m×|Q≡e|), where |Q≡e| denotes the number of states of the equation automaton, by an epsilon-removal and Bubenzer minimization algorithm of an Acyclic Deterministic Finite Automata (ADFA).
Journal Article
Model checking with generalized Rabin and Fin-less automata
In the automata theoretic approach to explicit state LTL model checking, the synchronized product of the model and an automaton that represents the negated formula is checked for emptiness. In practice, a (transition-based generalized) Büchi automaton (TGBA) is used for this procedure. This paper investigates whether using a more general form of acceptance, namely a transition-based generalized Rabin automaton (TGRA), improves the model checking procedure. TGRAs can have significantly fewer states than TGBAs; however, the corresponding emptiness checking procedure is more involved. With recent advances in probabilistic model checking and LTL to TGRA translators, it is only natural to ask whether checking a TGRA directly is more advantageous in practice. We designed a multi-core TGRA checking algorithm and performed experiments on a subset of the models and formulas from the 2015 Model Checking Contest and generated LTL formulas for models from the BEEM database. While we found little to no improvement by checking TGRAs directly, we show how various aspects of a TGRA’s structure influences the model checking performance. In this paper, we also introduce a Fin-less acceptance condition, which is a disjunction of TGBAs. We show how to convert TGRAs into automata with Fin-less acceptance and show how a TGBA emptiness procedure can be extended to check Fin-less automata.
Journal Article
From Tree Automata to String Automata Minimization
In this paper, we propose a reduction of the minimization problem for a bottom-up deterministic tree automaton (DFTA), making the latter a minimization of a string deterministic finite automaton (DFA). To achieve this purpose, we proceed first by the transformation of the tree automaton into a particular string automaton, followed by minimizing this string automaton. In addition, we show that for our transformation, the minimization of the resulting string automaton coincides with the minimization of the original tree automaton. Finally, we discuss the complexity of our proposal for different types of tree automata, namely: standard, acyclic, incremental, and incrementally constructed tree automata.
Journal Article
The algebra of binary trees is affine complete
A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. We show that on the algebra of binary trees whose leaves are labeled by letters of an alphabet containing at least three letters, a function is congruence preserving if and only if it is polynomial.
Journal Article
A Characterization for Decidable Separability by Piecewise Testable Languages
The separability problem for word languages of a class$\\mathcal{C}$by languages of a class$\\mathcal{S}$asks, for two given languages$I$and$E$from$\\mathcal{C}$ , whether there exists a language$S$from$\\mathcal{S}$that includes$I$and excludes$E$ , that is,$I \\subseteq S$and$S\\cap E = \\emptyset$ . In this work, we assume some mild closure properties for$\\mathcal{C}$and study for which such classes separability by a piecewise testable language (PTL) is decidable. We characterize these classes in terms of decidability of (two variants of) an unboundedness problem. From this, we deduce that separability by PTL is decidable for a number of language classes, such as the context-free languages and languages of labeled vector addition systems. Furthermore, it follows that separability by PTL is decidable if and only if one can compute for any language of the class its downward closure wrt. the scattered substring ordering (i.e., if the set of scattered substrings of any language of the class is effectively regular). The obtained decidability results contrast some undecidability results. In fact, for all (non-regular) language classes that we present as examples with decidable separability, it is undecidable whether a given language is a PTL itself. Our characterization involves a result of independent interest, which states that for any kind of languages$I$and$E$ , non-separability by PTL is equivalent to the existence of common patterns in$I$and$E$ .
Journal Article