Search

We are lifting classical combinatorial problems from single instances to regular sets of instances. The task of finding a positive instance of the combinatorial problem P in a potentially infinite given regular set is equivalent to the so called in t Reg -problem of P, which asks for a given DFA A, whether the intersection of P with L ( A ) is non-empty. The in t Reg -problem generalizes the idea of considering multiple instances at once and connects classical combinatorial problems with the field of automata theory. While the question of decidability of the in t Reg -problem has been answered positively for several NP and even PSPACE -complete problems, we are presenting some natural problems even from LOGSPACE with an undecidable in t Reg -problem. We also discuss alphabet sizes and different encoding-schemes elaborating the boundary between problem-variants with a decidable respectively undecidable in t Reg -problem.

The present paper is devoted to traversing a maze by a collective of automata. This part of automata theory gave rise to a fairly wide range of diverse problems ([1], [2]), including those related to problems of the theory of computational complexity and probability theory. It turns out that the consideration of complicated algebraic objects, such as Burnside groups, can be interesting in this context. In the paper, we show that the Cayley graph a finitely generated group cannot be traversed by a collective of automata if and only if the group is infinite and its every element is periodic.

Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information-theoretically optimal number of bits along with supporting queries on them efficiently. Towards this goal, we first design a succinct data structure for representing any deterministic finite automaton $\mathcal{D}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $(\sigma-1) n\log n + O(n \log \sigma)$ bits of space, which can determine, given an input string $x$ over $\Sigma$, whether $\mathcal{D}$ accepts $x$ in $O(|x| \log \sigma)$ time, using constant words of working space. When the input deterministic finite automaton is acyclic, not only we can improve the above space-bound significantly to $(\sigma -1) (n-1)\log n+ 3n + O(\log^2 \sigma) + o(n)$ bits, we also obtain optimal query time for string acceptance checking. More specifically, using our succinct representation, we can check if a given input string $x$ can be accepted by the acyclic deterministic finite automaton using time proportional to the length of $x$, hence, the optimal query time. We also exhibit a succinct data structure for representing a non-deterministic finite automaton $\mathcal{N}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $\sigma n^2+n$ bits of space, such that given an input string $x$, we can decide whether $\mathcal{N}$ accepts $x$ efficiently in $O(n^2|x|)$ time. Finally, we also provide time and space-efficient algorithms for performing several standard operations such as union, intersection, and complement on the languages accepted by deterministic finite automata.

Nowadays, certain problems in automata theory, manufacturing systems, telecommunication networks, parallel processing systems and traffic control are intimately linked with linear systems over tropical semirings. Due to non-invertibility of matrices—except monomial matrices—over certain semirings, we cannot generally take advantage of having the inverse of the coefficient matrix of a system to solve it. The main purpose of this paper is to introduce two methods based on the pseudo-inverse of a matrix for solving a linear system of equations over tropical semirings. To this end, under suitable conditions, we first reduce the order of the system through some row–column operational analysis. We then present a necessary and sufficient condition for the system to have a maximal solution. This solution is also obtained through a new version of Cramer’s rule for overdetermined system of equations. Finally, some illustrative examples are given to show the efficiency of the proposed methods, and Maple procedures are also included in the end.

In this paper, we study two important problems related to quasi-multiautomata: the complicated nature of verification of the GMAC condition for systems of quasi-multiautomata, and the fact that the nature of quasi-multiautomata has deviated from the original nature of automata as seen by the theory of formal languages. For the former problem, we include several new conditions that simplify the procedure. For the latter problem, we close this gap by presenting a construction of quasi-multiautomata, which corresponds to deterministic automata of the theory of formal languages and is based on the operation of concatenation.

We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the relationship between first-order logic and finite automata, and use this relationship to solve several problems involving sums of numbers defined by their base-2 and Fibonacci representations. Next, we turn to harder results. Recently, Cilleruelo, Luca, & Baxter proved, for all bases b ≥ 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome (Cilleruelo et al., Math. Comput. 87, 3023–3055, 2018). However, the cases b = 2, 3, 4 were left unresolved. We prove that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem of palindromes as an additive basis. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof.

Graph theory plays crucial role in structuring many real-world problems including, medical sciences, control theory, expert systems and network security. Product in graphs, an operation that consider two graphs and produce a new graph by simple or complex changes, has wide range of applications in games theory, automata theory, structural mechanics and networking system. An intuitionistic fuzzy model is used to handle the vagueness and uncertainty in network problems. A Pythagorean fuzzy model is a powerful tool for describing vagueness and uncertainty more accurately as compared to intuitionistic fuzzy model. The objective of this paper is to apply the concept of Pythagorean fuzzy sets to graphs and then combine two Pythagorean fuzzy graphs (PFGs) using two new graph products namely, maximal product and the residue product. This research paper investigates the regularity for these products. Moreover, it discusses some eminent properties such as strongness, connectedness and completeness. Further, it proposes some necessary and sufficient conditions for $${\mathscr {G}}_{1}*{\mathscr {G}}_{2}$$ and $${\mathscr {G}}_{1}\cdot {\mathscr {G}}_{2}$$ to be regular. Finally, decision-making problems concerning evaluation of best company for investment and alliance partner selection of a software company are solved to better understand PFGs.

This paper is towards the algebraic and topological study of automata based on residuated and co-residuated lattices via different operators. The interrelationships among the operators are discussed. Interestingly, we show that the algebraic concepts of an automaton based on a residuated and co-residuated lattice can be expressed in terms of [Formula: see text]-topology/co-topology induced by operators. Finally, a composition of such automata is introduced and its categorical significance is discussed.

The main objective of our paper is to focus on the study of sequences (finite or countable) of groups and hypergroups of linear differential operators of decreasing orders. By using a suitable ordering or preordering of groups linear differential operators we construct hypercompositional structures of linear differential operators. Moreover, we construct actions of groups of differential operators on rings of polynomials of one real variable including diagrams of actions–considered as special automata. Finally, we obtain sequences of hypergroups and automata. The examples, we choose to explain our theoretical results with, fall within the theory of artificial neurons and infinite cyclic groups. Hlavním cílem článku je studium posloupností (konečných nebo spočetných) grup a hypergrup lineárních diferenciálních operátorů klesajících řádů. Za použití vhodného uspořádání nebo předuspořádání grup lineárních diferenciálních operátorů konstruujeme hyperkompoziční struktury lineárních diferenciálních operátorů. Dále konstruujeme akce grup diferenciálních operátorů na okruzích polynomů jedné proměnné, a to včetně konstrukce diagramů těchto akcí, považovaných za automaty. Konečně, v článku získáváme posloupnosti hypergrup a automatů. Příklady, na kterých ilustrujeme teoretické výsledky článku, spadají do teorie umělých neuronů a nekonečných cyklických grup.

Here we give a selection of instructional examples of holonomy decompositions of finite transformation semigroups. These are edge cases that can be used in verifying computational implementations, as counterexamples in learning the holonomy method of the Krohn-Rhodes Theorem, and they are also sources of open problems.

In this paper we introduce the notion of derivation in product (direct product) of additively idempotent semirings. These semirings are useful and important tools in diverse areas such as design of switching circuits, automata theory, information systems, dynamic programming and decision theory. We study hereditary derivations, inner derivations and obtain a representation of an arbitrary derivations which are zero on the multipliers.

We investigate the constrained synchronization problem for weakly acyclic, or partially ordered, input automata. We show that, for input automata of this type, the problem is always in \(\textsf {NP}\). Furthermore, we give a full classification of the realizable complexities for constraint automata with at most two states and over a ternary alphabet. We find that most constrained problems that are PSPACE-complete in general become NP-complete. However, there also exist constrained problems that are PSPACE-complete in the general setting but become polynomial time solvable when considered for weakly acyclic input automata. We also investigate two problems related to subset synchronization, namely if there exists a word mapping all states into a given target subset of states, and if there exists a word mapping one subset into another. Both problems are \(\textsf {PSPACE}\)-complete in general, but in our setting the former is polynomial time solvable and the latter is \(\textsf {NP}\)-complete.

Consider the following one-player game. Take a well-formed sequence of opening and closing brackets (a Dyck word). As a move, the player can pair any opening bracket with any closing bracket to its right, erasing them. The goal is to re-pair (erase) the entire sequence, and the cost of a strategy is measured by its width: the maximum number of nonempty segments of symbols (separated by blank space) seen during the play.\ud \ud For various initial sequences, we prove upper and lower bounds on the minimum width sufficient for re-pairing. (In particular, the sequence associated with the complete binary tree of height n admits a strategy of width sub-exponential in log n.) Our two key contributions are (1) lower bounds on the width and (2) their application in automata theory: quasi-polynomial lower bounds on the translation from one-counter automata to Parikh-equivalent nondeterministic finite automata. The latter result answers a question by Atig et al. (2016).

We introduce a systematic method of approximating finite-time transition probabilities for continuous-time insertion-deletion models on sequences. The method uses automata theory to describe the action of an infinitesimal evolutionary generator on a probability distribution over alignments, where both the generator and the alignment distribution can be represented by Pair Hidden Markov Models (Pair HMMs). In general, combining HMMs in this way induces a multiplication of their state spaces; to control this, we introduce a coarse-graining operation to keep the state space at a constant size. This leads naturally to ordinary differential equations for the evolution of the transition probabilities of the approximating Pair HMM. The TKF model emerges as an exact solution to these equations for the special case of single-residue indels. For the general case, the equations can be solved by numerical integration. Using simulated data we show that the resulting distribution over alignments, when compared to previous approximations, is a better fit over a broader range of parameters. We also propose a related approach to develop differential equations for sufficient statistics to estimate the underlying instantaneous indel rates by Expectation-Maximization. Our code and data are available athttps://github.com/ihh/trajectory-likelihood.

We discuss some applications of WQOs to several fields were hierarchies and reducibilities are the principal classification tools, notably to Descriptive Set Theory, Computability theory and Automata Theory. While the classical hierarchies of sets usually degenerate to structures very close to ordinals, the extension of them to functions requires more complicated WQOs, and the same applies to reducibilities. We survey some results obtained so far and discuss open problems and possible research directions.

The article gives a description of the vulnerabilities detection model in case of unstable network interactions with the automated system (AS). The process of detection of AS vulnerabilities in these conditions has the following drawbacks: a narrow scope of application of the existing models, low responsiveness level and lack of completeness of the AS actual condition, low reliability of control results. On the basis of the automata theory a structural model has been constructed that ensures detection of AS vulnerabilities in the reviewed conditions. The process of the model’s operation in conditions of unstable network interactions with the AS is described. A flow chart of the algorithm that provides a possibility for practical implementation of the proposed model is constructed. The vulnerability detection model, which is presented in the article makes it possible to ensure promptness, completeness and reliability of monitoring the real condition of ASs functioning in unstable network interactions; to expand the scope of application of the existing models and methods for identifying vulnerabilities for dynamic AS featured by a relatively short time interval of operation; to automate the process of restoring control over AS interrupted by external factors; adaptively manage the decision-making time; to provide the iterative approach to identifying the AS vulnerabilities.

A k-limited automaton is a linear bounded automaton that may rewrite each tape cell only in the first k visits, where k ≥ 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate the descriptional complexity of limited automata. Since the unary languages accepted are necessarily regular, we first study the cost in the number of states when finite automata simulate a unary k-limited automaton. For the conversion of a 4n-state deterministic 1-limited automaton into one-way or two-way deterministic or nondeterministic finite automata, we show a lower bound of n ⋅ F ( n ) states, where F denotes Landau's function. So, even the ability to deterministically rewrite any cell only once gives an enormous descriptional power. For the simulation cost for removing the ability to rewrite each cell k ≥ 1 times, more precisely, the cost for the simulation of sweeping unary k-limited automata by deterministic finite automata, we obtain a lower bound of n ⋅ F ( n ) k . The upper bound of the cost for the simulation by two-way deterministic finite automata is a polynomial whose degree is quadratic in k. If the k-limited automaton is rotating, the upper bound reduces to O ( n k + 1 ) and the lower bound derived is Ω ( n k + 1 ) even for nondeterministic two-way finite automata. So, for rotating k-limited automata, the trade-off for the simulation is tight in the order of magnitude. Finally, we consider the simulation of k-limited automata over general alphabets by pushdown automata. It turns out that the cost is an exponential blow-up of the size. Furthermore, an exponential size is also necessary.

Recently, the minimum number of reticulation events that is required to simultaneously embed a collection P of rooted binary phylogenetic trees into a so-called temporal network has been characterized in terms of cherry-picking sequences. Such a sequence is a particular ordering on the leaves of the trees in P. However, it is well-known that not all collections of phylogenetic trees have a cherry-picking sequence. In this paper, we show that the problem of deciding whether or not P has a cherry-picking sequence is NP-complete for when P contains at least eight rooted binary phylogenetic trees. Moreover, we use automata theory to show that the problem can be solved in polynomial time if the number of trees in P and the number of cherries in each such tree are bounded by a constant., Accepted for publication in Theoretical Computer Science

Two models of automata over infinite alphabets are presented, mainly with a focus on the alphabet [Formula: see text]. In the first model, transitions can refer to logic formulas that connect properties of successive letters. In the second, the letters are considered as columns of a labeled grid which an automaton traverses column by column. Thus, both models focus on the comparison of successive letters, i.e. “local changes”. We prove closure (and non-closure) properties, show the decidability of the respective non-emptiness problems, prove limits on decidability results for extended models, and discuss open issues in the development of a generalized theory.

Nondeterminism gives computation models the power of existential choice. As a generalization of nondeterminism, “alternation” gives computation models the power of existential choice and universal choice simultaneously. In this paper, we extend fuzzy nondeterministic automata to a model called fuzzy alternating automata over distributive lattices. Compared with the previous work, a weight labels a leaf node of the run tree rather than be involved in the edge between states when executing a transition. One advantage of our setting is that it is easy to complement a given fuzzy alternating automaton. It suffices to take the dual operation on the transition function and negate final costs on states. Moreover, we show that fuzzy alternating automata have the same expressive power as fuzzy nondeterministic automata, and the former ones are exponentially more succinct than the latter ones. In addition, we illustrate that such exponential blow-up is unavoidable.

Alternation was first proposed by Chandra et al. for obtaining a theoretical model of parallel computations. Compared with nondeterminism, alternation gives computing devices the power of universal choice in addition to existential choice. In this paper, we put forward a notion of fuzzy alternating Buchi automata over a distributive lattice L ( L -ABAs, for short). In our setting, a weight is the label of a leaf node of the run tree when executing a transition, which is helpful in complementing L -ABAs. Taking the dual operation on the transition function and negating final costs on states, we can get the complement of a given L -ABA. We point out that L -ABAs have the same expressive power as L -valued fuzzy nondeterministic Buchi automata ( L -NBAs). A construction presented here shows that languages accepted by L -valued fuzzy alternating co-Buchi automata ( L -ACAs) are also ω-regular languages. Moreover, closure properties of L -ABAs and decision problems for L -ABAs are also discussed.

A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where \(k\ge 0\) is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k-limited automata towards their ability to perform reversible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all \(k\ge 0\), sweeping k-limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0-limited automata. Then we study the computational power gained in the number k of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every k and \(k+3\) rewrite operations. Finally, it turns out that all k-limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages.

In the last years, various extensions of ω-regular languages have been proposed in the literature, including ωB-regular (ω-regular languages extended with boundedness), ωS-regular (ω-regular languages extended with strict unboundedness), and ωBS-regular languages (the combination of ωB- and ωS-regular ones). While the first two classes satisfy a generalized closure property, namely, the complement of an ωB-regular (resp., ωS-regular) language is an ωS-regular (resp., ωB-regular) one, the last class is not closed under complementation. The existence of non-ωBS-regular languages that are the complements of some ωBS-regular ones and express fairly natural properties of reactive systems motivates the search for other well-behaved classes of extended ω-regular languages. In this paper, we introduce the class of ωT-regular languages, that includes meaningful languages which are not ωBS-regular. We first define it in terms of ωT-regular expressions. Then, we introduce a new class of automata (counter-check automata) and we prove that (i) their emptiness problem is decidable in PTIME and (ii) they are expressive enough to capture ωT-regular languages (whether or not ωT-regular languages are expressively complete with respect to counter-check automata is still an open problem). Finally, we provide an encoding of ωT-regular expressions into S1S+U.

Theories of fuzzy sets and type-2 fuzzy sets are powerful mathematical tools for modeling various types of uncertainty. In this paper we introduce the concept of type-2 fuzzy finite state automata and discuss the algebraic study of type-2 fuzzy finite state automata, i.e., to introduce the concept of homomorphisms between two type-2 fuzzy finite state automata, to associate a type-2 fuzzy transformation semigroup with a type-2 fuzzy finite state automata. Finally, we discuss several product of type-2 fuzzy finite state automata and shown that these product is a categorical product.

In the paper we investigate automata whose state sets and sets of output symbols are endowed with algebraic structures of hypergraphs. Universal hypergraphic automata are universally attracting objects in the category of such automata. The main result is a solving of the problem of concrete characterization of universal hypergraphic automata.

One-way multi-head finite automata are considered towards their ability to perform reversible computations. It is shown that, for every number k ≥ 1 of heads, there are problems which can be solved by one-way k-head finite automata, but not by any one-way reversible k-head finite automaton. Additionally, a proper head hierarchy is obtained for one-way reversible multi-head finite automata. Closure properties and decidability problems are investigated as well. It turns out that one-way reversible finite automata with two heads are still a powerful model, since almost all commonly studied problems are not even semidecidable. Finally, descriptional complexity aspects are studied and non-recursive trade-offs are shown.

Already in the seventies, strong results illustrating the intimate relationship between category theory and automata theory have been described and are still investigated. In this column, we provide a uniform presentation of the basic concepts that underlie minimization results in automata theory. We then use this knowledge for introducing a new model of automata that is an hybrid of deterministic finite automata and automata weighted over a field. These automata are very natural, and enjoy minimization result by design. The presentation of this paper is indeed categorical in essence, but it assumes no prior knowledge from the reader. It is also non-conventional in that it is neither algebraic, nor co-algebraic oriented.

Finite languages are an important sub-regular language family, which were intensively studied during the last two decades in particular from a descriptional complexity perspective. An important contribution to the theory of finite languages are the deterministic and the recently introduced nondeterministic finite cover automata (DFCAs and NFCAs, respectively) as an alternative representation of finite languages by ordinary finite automata. We compare these two types of cover automata from a descriptional complexity point of view, showing that these devices have a lot in common with ordinary finite automata. In particular, we study how to adapt lower bound techniques for nondeterministic finite automata to NFCAs such as, e.g., the biclique edge cover technique, solving an open problem from the literature. Moreover, the trade-off of conversions between DFCAs and NFCAs as well as between finite cover automata and ordinary finite automata are investigated. Finally, we present some results on the average size of finite cover automata.

We present a disambiguation algorithm for weighted automata. The algorithm admits two main stages: a pre-disambiguation stage followed by a transition removal stage. We give a detailed description of the algorithm and the proof of its correctness. The algorithm is not applicable to all weighted automata but we prove sufficient conditions for its applicability in the case of the tropical semiring by introducing the weak twins property . In particular, the algorithm can be used with any weighted automaton over the tropical semiring for which the weighted determinization algorithm terminates and with any acyclic weighted automaton over an arbitrary weakly left divisible cancellative and commutative semiring. While disambiguation can sometimes be achieved using weighted determinization, our disambiguation algorithm in some cases can return a result that is exponentially smaller than any equivalent deterministic automaton. We also present some empirical evidence of the space benefits of disambiguation over determinization in speech recognition and machine translation applications.

We continue our research on minimization problems and related problems for automata w.r.t. to different error profiles, now considering nondeterministic finite automata (NFAs) as inputs. Here the error profiles are almost-equivalence and E-equivalence. We show that the minimization problems and their underlying equivalence problems become PSPACE-complete in most cases. The obtained results nicely fit to the known ones on ordinary NFA minimization, and show a significant difference to the previously obtained results on deterministic finite state machines.

We prove completeness for some language-theoretic models of the full Lambek calculus and its various fragments. First we consider syntactic concepts and syntactic concepts over regular languages, which provide a complete semantics for the full Lambek calculus $${\mathbf {FL}}_\perp $$FLź. We present a new semantics we call automata-theoretic, which combines languages and relations via closure operators which are based on automaton transitions. We establish the completeness of this semantics for the full Lambek calculus via an isomorphism theorem for the syntactic concepts lattice of a language and a construction for the universal automaton recognizing the same language. Finally, we use automata-theoretic semantics to prove completeness of relation models of binary relations and finite relation models for the Lambek calculus without and with empty antecedents (henceforth: $$\mathbf L $$L and $$\mathbf L1 $$L1), thus solving a problem left open by Pentus (Ann Pure Appl Log 75:179---213, 1995).

Automata theory based on complete residuated lattice-valued logic has been initiated by Qiu, and further systematically established by Qiu et al. In this paper, we propose the notion of nondeterministic fuzzy automata with membership values in a complete residuated lattice L, called lattice-valued nondeterministic fuzzy automata (L-NFAs). In our setting, a state of an L-NFA may have more than one transition labeled by the same input symbol, which reflects nondeterminism. To compare the behaviors of L-NFAs, we introduce two language equivalence relations which have different discriminating power. Furthermore, we extend the two relations to the complete residuated lattice-valued setting and investigate their properties such as robustness and compositionality. The theory developed here is applicable to the quantitative modeling and verification of fuzzy systems. Present a new kind of nondeterministic fuzzy automata.Introduce two language-equivalent relations and their fuzzy versions.Analyze the compositionality and robustness of the two relations.

A term, also called a tree, is said to be linear, if each variable occurs in the term only once. The linear terms and sets of linear terms, the so-called linear tree languages, play some role in automata theory and in the theory of formal languages in connection with recognizability. We define a partial superposition operation on sets of linear trees of a given type τ and study the properties of some many-sorted partial clones that have sets of linear trees as elements and partial superposition operations as fundamental operations. The endomorphisms of those algebras correspond to nondeterministic linear hypersubstitutions.

We first outline main steps and achievements along Bertoni's research path in quantum finite automata theory from the very basic definitions of the models of quantum finite automata throughout the investigation of their computational and descriptional power. Next, we choose to focus on Bertoni's studies on quantum finite automata descriptional complexity. In particular, we expand on a statistical framework for the synthesis of succinct quantum finite automata, discussing its adaptation to the case of multiperiodic events and languages. We then improve such a framework to obtain even more succinct quantum finite automata for some multiperiodic languages. Finally, we introduce some promise problems for multiperiodic inputs, showing that even on this class of problems the descriptional power of quantum finite automata greatly outperforms that of equivalent classical finite automata. We build small size Monte Carlo quantum finite automata for multiperiodic languages.We analyze the modular architecture of such Monte Carlo quantum finite automata.We solve promise problems on multiperiodic inputs by small quantum finite automata.

We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M′ within distance ρ from M satisfy (or violate) φ. The model-measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification; robustness problems that measure how much a model can be perturbed without violating the specification; and parameter synthesis for hybrid systems. We show that for automatic distance functions, and (a) ω-regular linear-time, (b) ω-regular branching-time, and (c) hybrid specifications, the model-measuring problem can be solved. We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for word, tree, and hybrid automata by the optimal-value question for the weighted versions of these automata. For automata over words and trees, we consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. For hybrid automata, we consider monotonic (parametric) hybrid automata, a hybrid counterpart of (discrete) weighted automata. We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications. Further, we propose the modeling framework for model measuring to ease the specification and reduce the likelihood of errors in modeling. Finally, we present a variant of the model-measuring problem, called the model-repair problem. The model-repair problem applies to models that do not satisfy the specification; it can be used to derive restrictions, under which the model satisfies the specification, i.e., to repair the model.

In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of finite automata with multiple independent heads that walk on Cayley graphs, called group-walking automata, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines, and those on which the head hierarchy is infinite.

The degree of ambiguity counts the number of accepting computations of a nondeterministic finite automaton (NFA) on a given input. Alternatively, the nondeterminism of an NFA can be measured by counting the amount of guessing in a single computation or the number of leaves of the computation tree on a given input. This paper surveys work on the degree of ambiguity and on various nondeterminism measures for finite automata. In particular, we focus on state complexity comparisons between NFAs with quantified ambiguity or nondeterminism.

Automata theory plays a key role in computational theory as many computational problems can be solved with its help. Formal grammar is a special type of automata designed for linguistic purposes. Formal grammar generates formal languages. Rough grammar and rough languages were introduced to incorporate the imprecision of real languages in formal languages. These languages have limitations on uncertainty. The authors have considered both uncertainty and approximations to define rough fuzzy grammar and rough fuzzy languages. Under certain restrictions, their grammar reduces to formal grammar. Furthermore, the authors have proposed definition of rough fuzzy automata that accepts rough fuzzy regular language.

The family of languages recognized by deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under concatenation, Kleene star and reversal (under natural assumptions on the partition of the alphabet). As shown by Alur and Madhusudan (2004) 2, the Kleene star and the reversal of an n-state IDPDA can be represented by an IDPDA with 2 O ( n 2 ) states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2 O ( ( m + n ) 2 ) states. This paper presents more efficient constructions for the Kleene star and for the reversal, which yield 2 ( n log n ) states, as well as an m 2 ( n log n ) -state construction for the concatenation. These constructions are optimal up to a factor in the exponent, due to the close lower bounds previously established by Piao and Salomaa (2009) 27.