5,084 results on '"automata theory"'
Number of results to display per page
Search Results
52. Sliding Window Algorithms for Regular Languages
- Author
-
Ganardi, Moses, Hucke, Danny, Lohrey, Markus, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Klein, Shmuel Tomi, editor, Martín-Vide, Carlos, editor, and Shapira, Dana, editor
- Published
- 2018
- Full Text
- View/download PDF
53. Algorithmic verification problems in automata-theoretic settings
- Author
-
Bundala, Daniel and Ouaknine, Joel
- Subjects
005.1 ,Application software ,Algorithms ,Computer science--Mathematics ,temporal logic ,bounded model checking ,automata theory ,formal verification ,parametric timed automata - Abstract
Problems in formal verification are often stated in terms of finite automata and extensions thereof. In this thesis we investigate several such algorithmic problems. In the first part of the thesis we develop a theory of completeness thresholds in Bounded Model Checking. A completeness threshold for a given model M and a specification φ is a bound k such that, if no counterexample to φ of length k or less can be found in M, then M in fact satisfies φ. We settle a problem of Kroening et al. [KOS
+ 11] in the affirmative, by showing that the linearity problem for both regular and ω-regular specifications (provided as finite automata and Buchi automata respectively) is PSPACE-complete. Moreover, we establish the following dichotomies: for regular specifications, completeness thresholds are either linear or exponential, whereas for ω-regular specifications, completeness thresholds are either linear or at least quadratic in the recurrence diameter of the model under consideration. Given a formula in a temporal logic such as LTL or MTL, a fundamental problem underpinning automata-based model checking is the complexity of evaluating the formula on a given finite word. For LTL, the complexity of this task was recently shown to be in NC [KF09]. In the second part of the thesis we present an NC algorithm for MTL, a quantitative (or metric) extension of LTL, and give an AC1 algorithm for UTL, the unary fragment of LTL. We then establish a connection between LTL path checking and planar circuits which, among others, implies that the complexity of LTL path checking depends on the Boolean connectives allowed: adding Boolean exclusive or yields a temporal logic with P-complete path-checking problem. In the third part of the thesis we study the decidability of the reachability problem for parametric timed automata. The problem was introduced over 20 years ago by Alur, Henzinger, and Vardi [AHV93]. It is known that for three or more parametric clocks the problem is undecidable. We translate the problem to reachability questions in certain extensions of parametric one-counter machines. By further reducing to satisfiability in Presburger arithmetic with divisibility, we obtain decidability results for several classes of parametric one-counter machines. As a corollary, we show that, in the case of a single parametric clock (with arbitrarily many nonparametric clocks) the reachability problem is NEXP-complete, improving the nonelementary decision procedure of Alur et al. The case of two parametric clocks is open. Here, we show that the reachability is decidable in this case of automata with a single parameter.- Published
- 2014
54. Proving properties of some greedily-defined integer recurrences via automata theory.
- Author
-
Shallit, Jeffrey
- Abstract
Venkatachala on the one hand, and Avdispahić & Zejnulahi on the other, both studied integer sequences with an unusual sum property defined in a greedy way, and proved many results about them. However, their proofs were rather lengthy and required numerous cases. In this paper, I provide a different approach, via finite automata, that can prove the same results (and more) in a simple, unified way. Instead of case analysis, we use a decision procedure implemented in the free software Walnut. Using these ideas, we can prove a conjecture of Quet and find connections between Quet's sequence and the "married" functions of Hofstadter. • Uses a new technique, automata theory, to prove properties of some greedily-defined integer sequences. • Finds much simpler proofs of some known results in the literature. • Finds a new connection between Quet's sequence and the Hofstadter married functions. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
55. Repairing strings and trees
- Author
-
Riveros Jaeger, Cristian and Benedikt, Michael
- Subjects
005.14 ,Computer science (mathematics) ,Theory and automated verification ,Automata theory ,repair ,edit distance ,strings ,trees ,tree automata ,XML Schema - Abstract
What do you do if a computational object fails a specification? An obvious approach is to repair it, namely, to modify the object minimally to get something that satisfies the constraints. In this thesis we study foundational problems of repairing regular specifications over strings and trees. Given two regular specifications R and T we aim to understand how difficult it is to transform an object satisfying R into an object satisfying T. The setting is motivated by considering R to be a restriction -- a constraint that the input object is guaranteed to satisfy -- while T is a target -- a constraint that we want to enforce. We first study which pairs of restriction and target specifications can be repaired with a ``small'' numbers of changes. We formalize this as the bounded repair problem -- to determine whether one can repair each object satisfying R into T with a uniform number of edits. We provide effective characterizations of the bounded repair problem for regular specifications over strings and trees. These characterizations are based on a good understanding of the cyclic behaviour of finite automata. By exploiting these characterizations, we give optimal algorithms to decide whether two specifications are bounded repairable or not. We also consider the impact of limitations on the editing process -- what happens when we require the repair to be done sequentially over serialized objects. We study the bounded repair problem over strings and trees restricted to this streaming setting and show that this variant can be characterized in terms of finite games. Furthermore, we use this characterization to decide whether one can repair a pair of specifications in a streaming fashion with bounded cost and how to obtain a streaming repair strategy in this case. The previous notion asks for a uniform bound on the number of edits, but having this property is a strong requirement. To overcome this limitation, we study how to calculate the maximum number of edits per character needed to repair any object in R into T. We formalize this as the asymptotic cost -- the limit of the number of edits divided by the length of the input in the worst case. Our contribution is an algorithm to compute the asymptotic cost for any pair of regular specifications over strings. We also consider the streaming variant of this cost and we show how to compute it by reducing this problem to mean-payoff games.
- Published
- 2013
56. On Computational Complexity of Set Automata
- Author
-
Rubtsov, Alexander A., Vyalyi, Mikhail N., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Charlier, Émilie, editor, Leroy, Julien, editor, and Rigo, Michel, editor
- Published
- 2017
- Full Text
- View/download PDF
57. Deduplication on Finite Automata and Nested Duplication Systems
- Author
-
Cho, Da-Jung, Han, Yo-Sub, Kim, Hwee, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Patitz, Matthew J., editor, and Stannett, Mike, editor
- Published
- 2017
- Full Text
- View/download PDF
58. On the membership problem for pattern languages and related topics
- Author
-
Schmid, Markus L.
- Subjects
401 ,Formal language theory ,Automata theory ,Pattern Languages ,Membership problem ,NP-complete problems - Abstract
In this thesis, we investigate the complexity of the membership problem for pattern languages. A pattern is a string over the union of the alphabets A and X, where X := {x_1, x_2, x_3, ...} is a countable set of variables and A is a finite alphabet containing terminals (e.g., A := {a, b, c, d}). Every pattern, e.g., p := x_1 x_2 a b x_2 b x_1 c x_2, describes a pattern language, i.e., the set of all words that can be obtained by uniformly substituting the variables in the pattern by arbitrary strings over A. Hence, u := cacaaabaabcaccaa is a word of the pattern language of p, since substituting cac for x_1 and aa for x_2 yields u. On the other hand, there is no way to obtain the word u' := bbbababbacaaba by substituting the occurrences of x_1 and x_2 in p by words over A. The problem to decide for a given pattern q and a given word w whether or not w is in the pattern language of q is called the membership problem for pattern languages. Consequently, (p, u) is a positive instance and (p, u') is a negative instance of the membership problem for pattern languages. For the unrestricted case, i.e., for arbitrary patterns and words, the membership problem is NP-complete. In this thesis, we identify classes of patterns for which the membership problem can be solved efficiently. Our first main result in this regard is that the variable distance, i.e., the maximum number of different variables that separate two consecutive occurrences of the same variable, substantially contributes to the complexity of the membership problem for pattern languages. More precisely, for every class of patterns with a bounded variable distance the membership problem can be solved efficiently. The second main result is that the same holds for every class of patterns with a bounded scope coincidence degree, where the scope coincidence degree is the maximum number of intervals that cover a common position in the pattern, where each interval is given by the leftmost and rightmost occurrence of a variable in the pattern. The proof of our first main result is based on automata theory. More precisely, we introduce a new automata model that is used as an algorithmic framework in order to show that the membership problem for pattern languages can be solved in time that is exponential only in the variable distance of the corresponding pattern. We then take a closer look at this automata model and subject it to a sound theoretical analysis. The second main result is obtained in a completely different way. We encode patterns and words as relational structures and we then reduce the membership problem for pattern languages to the homomorphism problem of relational structures, which allows us to exploit the concept of the treewidth. This approach turns out be successful, and we show that it has potential to identify further classes of patterns with a polynomial time membership problem. Furthermore, we take a closer look at two aspects of pattern languages that are indirectly related to the membership problem. Firstly, we investigate the phenomenon that patterns can describe regular or context-free languages in an unexpected way, which implies that their membership problem can be solved efficiently. In this regard, we present several sufficient conditions and necessary conditions for the regularity and context-freeness of pattern languages. Secondly, we compare pattern languages with languages given by so-called extended regular expressions with backreferences (REGEX). The membership problem for REGEX languages is very important in practice and since REGEX are similar to pattern languages, it might be possible to improve algorithms for the membership problem for REGEX languages by investigating their relationship to patterns. In this regard, we investigate how patterns can be extended in order to describe large classes of REGEX languages.
- Published
- 2012
59. Generalized simulation relations with applications in automata theory
- Author
-
Clemente, Lorenzo, Mayr, Richard., and Etessami, Kousha
- Subjects
004.01 ,computer science ,automata theory ,simulation preorder ,minimization - Abstract
Finite-state automata are a central computational model in computer science, with numerous and diverse applications. In one such application, viz. model-checking, automata over infinite words play a central rˆole. In this thesis, we concentrate on B¨uchi automata (BA), which are arguably the simplest finite-state model recognizing languages of infinite words. Two algorithmic problems are paramount in the theory of automata: language inclusion and automata minimization. They are both PSPACE-complete, thus under standard complexity-theoretic assumptions no deterministic algorithm with worst case polynomial time can be expected. In this thesis, we develop techniques to tackle these problems. In automata minimization, one seeks the smallest automaton recognizing a given language (“small” means with few states). Despite PSPACE-hardness of minimization, the size of an automaton can often be reduced substantially by means of quotienting. In quotienting, states deemed equivalent according to a given equivalence are merged together; if this merging operation preserves the language, then the equivalence is said to be Good for Quotienting (GFQ). In general, quotienting cannot achieve exact minimization, but, in practice, it can still offer a very good reduction in size. The central topic of this thesis is the design of GFQ equivalences for B¨uchi automata. A particularly successful approach to the design of GFQ equivalences is based on simulation relations. Simulation relations are a powerful tool to compare the local behavior of automata. The main contribution of this thesis is to generalize simulations, by relaxing locality in three perpendicular ways: by fixing the input word in advance (fixed-word simulations, Ch. 3), by allowing jumps (jumping simulations, Ch. 4), and by using multiple pebbles (multipebble simulations for alternating BA, Ch. 5). In each case, we show that our generalized simulations induce GFQ equivalences. For fixed-word simulation, we argue that it is the coarsest GFQ simulation implying language inclusion, by showing that it subsumes a natural hierarchy of GFQ multipebble simulations. From a theoretical perspective, our study significantly extends the theory of simulations for BA; relaxing locality is a general principle, and it may find useful applications outside automata theory. From a practical perspective, we obtain GFQ equivalences coarser than previously possible. This yields smaller quotient automata, which is beneficial in applications. Finally, we show how simulation relations have recently been applied to significantly optimize exact (exponential) language inclusion algorithms (Ch. 6), thus extending their practical applicability.
- Published
- 2012
60. Weak cost automata over infinite trees
- Author
-
Vanden Boom, Michael T. and Ong, C.-H. L.
- Subjects
512 ,Computer science (mathematics) ,automata theory ,monadic second-order logic ,parity games ,cost functions - Abstract
Cost automata are traditional finite state automata enriched with a finite set of counters that can be manipulated on each transition. Based on the evolution of counter values, a cost automaton defines a function from the set of structures under consideration to the natural numbers extended with infinity, modulo a boundedness relation that ignores exact values but preserves boundedness properties. Historically, variants of cost automata have been used to solve problems in language theory such as the star height problem. They also have a rich theory in their own right as part of the theory of regular cost functions, which was introduced by Colcombet as an extension to the theory of regular languages. It subsumes the classical theory since a language can be associated with the function that maps every structure in the language to 0 and everything else to infinity; it is a strict extension since cost functions can count some behaviour within the input. Regular cost functions have been previously studied over finite words and trees. This thesis extends the theory to infinite trees, where classical parity automata are enriched with a finite set of counters. Weak cost automata, which have priorities {0,1} or {1,2} and an additional restriction on the structure of the transition function, are shown to be equivalent to a weak cost monadic logic. A new notion of quasi-weak cost automata is also studied and shown to arise naturally in this cost setting. Moreover, a decision procedure is given to determine whether or not functions definable using weak or quasi-weak cost automata are equivalent up to the boundedness relation, which also proves the decidability of the weak cost monadic logic over infinite trees. The semantics of these cost automata over infinite trees are defined in terms of cost-parity games which are two-player infinite games where one player seeks to minimize the counter values and satisfy the parity condition, and the other player seeks to maximize the counter values or sabotage the parity condition. The main contributions and key technical results involve proving that certain cost-parity games admit positional or finite-memory strategies. These results also help settle the decidability of some special cases of long-standing open problems in the classical theory. In particular, it is shown that it is decidable whether a regular language of infinite trees is recognizable using a nondeterministic co-Büchi automaton. Likewise, given a Büchi or co-Büchi automaton as input, it is decidable whether or not there is a weak automaton recognizing the same language.
- Published
- 2012
61. Complexity-aware Decision-making with Applications to Large-scale and Human-in-the-loop Systems
- Abstract
This thesis considers control systems governed by autonomous decision-makers and humans. We formalise and compute low-complex control policies with applications to large-scale systems, and propose human interaction models for controllers to compute interaction-aware decisions. In the first part of the thesis, we consider complexity-aware decision-making, formalising the complexity of control policies and constructing algorithms that compute low-complexity control policies. More precisely, first, we consider large-scale control systems given by hierarchical finite state machines (HFSMs) and present a planning algorithm for such systems that exploits the hierarchy to compute optimal policies efficiently. The algorithm can also handle changes in the system with ease. We prove these properties and conduct simulations on HFSMs with up to 2 million states, including a robot application, where our algorithm outperforms both Dijkstra's algorithm and Contraction Hierarchies. Second, we present a planning objective for control systems modelled as finite state machines yielding an explicit trade-off between a policy's performance and complexity. We consider Kolmogorov complexity since it captures the ultimate compression of an object on a universal Turing machine. We prove that this trade-off is hard to optimise in the sense that dynamic programming is infeasible. Nonetheless, we present two heuristic algorithms obtaining low-complexity policies and evaluate the algorithms on a simple navigation task for a mobile robot, where we obtain low-complexity policies that concur with intuition. In the second part of the thesis, we consider human-in-the-loop systems and predict human decision-making in such systems. First, we look at how the interaction between a robot and a human in a control system can be predicted using game theory, focusing on an autonomous truck platoon interacting with a human-driven car. The interaction is modelled as a hierarchical dynamic game, where the hie, Denna avhandling studerar styrsystem med autonoma beslutsfattare och människor. Vi formaliserar och beräknar styrlagar av låg komplexitet med tillämpningar på storskaliga system samt föreslår modeller för mänsklig interaktion som kan användas av regulatorer för att beräkna interaktionsmedvetna beslut. I den första delen av denna avhandling studerar vi komplexitet-medveten beslutsfattning, där vi formaliserar styrlagars komplexitet samt konstruerar algoritmer som beräknar styrlagar med låg komplexitet. Mer precist, först studerar vi storskaliga system givna av hierarkiska finita tillståndsmaskiner (HFSMs) och presenterar en planeringsalgoritm för sådana system som utnyttjar hierarkin för att beräkna optimala styrlagar effektivt. Algoritmen kan också lätt hantera förändringar i systemet. Vi bevisar dessa egenskaper och utför simuleringar på HFSMs med upp till 2 miljoner tillstånd, inklusive en robot-applikation, där vår algorithm överträffar både Dijkstra's algoritm och så kallade Contraction Hierarchies. För det andra så presenterar vi ett planeringsobjektiv för finita tillståndsmaskiner som ger en explicit avvägning mellan ett styrlags prestanda och komplexitet. Vi använder Kolmogorovkomplexitet då den fångar den ultimata komprimeringen av ett objekt i en universell Turing-maskin. Vi bevisar att detta objektiv är icke-trivial att optimera över i avseendet att dynamisk programming är omöjligt att utföra. Vi presenterar två algoritmer som beräknar styrlagar med låg komplexitet och evaluerar våra algoritmer på ett enkelt navigationsproblem där vi erhåller styrlagar av låg komplexitet som instämmer med intuition. I den andra delen av denna avhandling behandlar vi reglersystem där en människa interagerar med systemet och studerar hur mänskligt beslutsfattande i sådana system kan förutspås. Först studerar vi hur interaktionen mellan en maskin och en människa i ett reglersystem can förutspås med hjälp av spelteori, med fokus på en självkörande lastbilskonvoj som interagera, QC 20230523
- Published
- 2023
62. Complexity-aware Decision-making with Applications to Large-scale and Human-in-the-loop Systems
- Abstract
This thesis considers control systems governed by autonomous decision-makers and humans. We formalise and compute low-complex control policies with applications to large-scale systems, and propose human interaction models for controllers to compute interaction-aware decisions. In the first part of the thesis, we consider complexity-aware decision-making, formalising the complexity of control policies and constructing algorithms that compute low-complexity control policies. More precisely, first, we consider large-scale control systems given by hierarchical finite state machines (HFSMs) and present a planning algorithm for such systems that exploits the hierarchy to compute optimal policies efficiently. The algorithm can also handle changes in the system with ease. We prove these properties and conduct simulations on HFSMs with up to 2 million states, including a robot application, where our algorithm outperforms both Dijkstra's algorithm and Contraction Hierarchies. Second, we present a planning objective for control systems modelled as finite state machines yielding an explicit trade-off between a policy's performance and complexity. We consider Kolmogorov complexity since it captures the ultimate compression of an object on a universal Turing machine. We prove that this trade-off is hard to optimise in the sense that dynamic programming is infeasible. Nonetheless, we present two heuristic algorithms obtaining low-complexity policies and evaluate the algorithms on a simple navigation task for a mobile robot, where we obtain low-complexity policies that concur with intuition. In the second part of the thesis, we consider human-in-the-loop systems and predict human decision-making in such systems. First, we look at how the interaction between a robot and a human in a control system can be predicted using game theory, focusing on an autonomous truck platoon interacting with a human-driven car. The interaction is modelled as a hierarchical dynamic game, where the hie, Denna avhandling studerar styrsystem med autonoma beslutsfattare och människor. Vi formaliserar och beräknar styrlagar av låg komplexitet med tillämpningar på storskaliga system samt föreslår modeller för mänsklig interaktion som kan användas av regulatorer för att beräkna interaktionsmedvetna beslut. I den första delen av denna avhandling studerar vi komplexitet-medveten beslutsfattning, där vi formaliserar styrlagars komplexitet samt konstruerar algoritmer som beräknar styrlagar med låg komplexitet. Mer precist, först studerar vi storskaliga system givna av hierarkiska finita tillståndsmaskiner (HFSMs) och presenterar en planeringsalgoritm för sådana system som utnyttjar hierarkin för att beräkna optimala styrlagar effektivt. Algoritmen kan också lätt hantera förändringar i systemet. Vi bevisar dessa egenskaper och utför simuleringar på HFSMs med upp till 2 miljoner tillstånd, inklusive en robot-applikation, där vår algorithm överträffar både Dijkstra's algoritm och så kallade Contraction Hierarchies. För det andra så presenterar vi ett planeringsobjektiv för finita tillståndsmaskiner som ger en explicit avvägning mellan ett styrlags prestanda och komplexitet. Vi använder Kolmogorovkomplexitet då den fångar den ultimata komprimeringen av ett objekt i en universell Turing-maskin. Vi bevisar att detta objektiv är icke-trivial att optimera över i avseendet att dynamisk programming är omöjligt att utföra. Vi presenterar två algoritmer som beräknar styrlagar med låg komplexitet och evaluerar våra algoritmer på ett enkelt navigationsproblem där vi erhåller styrlagar av låg komplexitet som instämmer med intuition. I den andra delen av denna avhandling behandlar vi reglersystem där en människa interagerar med systemet och studerar hur mänskligt beslutsfattande i sådana system kan förutspås. Först studerar vi hur interaktionen mellan en maskin och en människa i ett reglersystem can förutspås med hjälp av spelteori, med fokus på en självkörande lastbilskonvoj som interagera, QC 20230523
- Published
- 2023
63. Complexity-aware Decision-making with Applications to Large-scale and Human-in-the-loop Systems
- Abstract
This thesis considers control systems governed by autonomous decision-makers and humans. We formalise and compute low-complex control policies with applications to large-scale systems, and propose human interaction models for controllers to compute interaction-aware decisions. In the first part of the thesis, we consider complexity-aware decision-making, formalising the complexity of control policies and constructing algorithms that compute low-complexity control policies. More precisely, first, we consider large-scale control systems given by hierarchical finite state machines (HFSMs) and present a planning algorithm for such systems that exploits the hierarchy to compute optimal policies efficiently. The algorithm can also handle changes in the system with ease. We prove these properties and conduct simulations on HFSMs with up to 2 million states, including a robot application, where our algorithm outperforms both Dijkstra's algorithm and Contraction Hierarchies. Second, we present a planning objective for control systems modelled as finite state machines yielding an explicit trade-off between a policy's performance and complexity. We consider Kolmogorov complexity since it captures the ultimate compression of an object on a universal Turing machine. We prove that this trade-off is hard to optimise in the sense that dynamic programming is infeasible. Nonetheless, we present two heuristic algorithms obtaining low-complexity policies and evaluate the algorithms on a simple navigation task for a mobile robot, where we obtain low-complexity policies that concur with intuition. In the second part of the thesis, we consider human-in-the-loop systems and predict human decision-making in such systems. First, we look at how the interaction between a robot and a human in a control system can be predicted using game theory, focusing on an autonomous truck platoon interacting with a human-driven car. The interaction is modelled as a hierarchical dynamic game, where the hie, Denna avhandling studerar styrsystem med autonoma beslutsfattare och människor. Vi formaliserar och beräknar styrlagar av låg komplexitet med tillämpningar på storskaliga system samt föreslår modeller för mänsklig interaktion som kan användas av regulatorer för att beräkna interaktionsmedvetna beslut. I den första delen av denna avhandling studerar vi komplexitet-medveten beslutsfattning, där vi formaliserar styrlagars komplexitet samt konstruerar algoritmer som beräknar styrlagar med låg komplexitet. Mer precist, först studerar vi storskaliga system givna av hierarkiska finita tillståndsmaskiner (HFSMs) och presenterar en planeringsalgoritm för sådana system som utnyttjar hierarkin för att beräkna optimala styrlagar effektivt. Algoritmen kan också lätt hantera förändringar i systemet. Vi bevisar dessa egenskaper och utför simuleringar på HFSMs med upp till 2 miljoner tillstånd, inklusive en robot-applikation, där vår algorithm överträffar både Dijkstra's algoritm och så kallade Contraction Hierarchies. För det andra så presenterar vi ett planeringsobjektiv för finita tillståndsmaskiner som ger en explicit avvägning mellan ett styrlags prestanda och komplexitet. Vi använder Kolmogorovkomplexitet då den fångar den ultimata komprimeringen av ett objekt i en universell Turing-maskin. Vi bevisar att detta objektiv är icke-trivial att optimera över i avseendet att dynamisk programming är omöjligt att utföra. Vi presenterar två algoritmer som beräknar styrlagar med låg komplexitet och evaluerar våra algoritmer på ett enkelt navigationsproblem där vi erhåller styrlagar av låg komplexitet som instämmer med intuition. I den andra delen av denna avhandling behandlar vi reglersystem där en människa interagerar med systemet och studerar hur mänskligt beslutsfattande i sådana system kan förutspås. Först studerar vi hur interaktionen mellan en maskin och en människa i ett reglersystem can förutspås med hjälp av spelteori, med fokus på en självkörande lastbilskonvoj som interagera, QC 20230523
- Published
- 2023
64. Complexity-aware Decision-making with Applications to Large-scale and Human-in-the-loop Systems
- Abstract
This thesis considers control systems governed by autonomous decision-makers and humans. We formalise and compute low-complex control policies with applications to large-scale systems, and propose human interaction models for controllers to compute interaction-aware decisions. In the first part of the thesis, we consider complexity-aware decision-making, formalising the complexity of control policies and constructing algorithms that compute low-complexity control policies. More precisely, first, we consider large-scale control systems given by hierarchical finite state machines (HFSMs) and present a planning algorithm for such systems that exploits the hierarchy to compute optimal policies efficiently. The algorithm can also handle changes in the system with ease. We prove these properties and conduct simulations on HFSMs with up to 2 million states, including a robot application, where our algorithm outperforms both Dijkstra's algorithm and Contraction Hierarchies. Second, we present a planning objective for control systems modelled as finite state machines yielding an explicit trade-off between a policy's performance and complexity. We consider Kolmogorov complexity since it captures the ultimate compression of an object on a universal Turing machine. We prove that this trade-off is hard to optimise in the sense that dynamic programming is infeasible. Nonetheless, we present two heuristic algorithms obtaining low-complexity policies and evaluate the algorithms on a simple navigation task for a mobile robot, where we obtain low-complexity policies that concur with intuition. In the second part of the thesis, we consider human-in-the-loop systems and predict human decision-making in such systems. First, we look at how the interaction between a robot and a human in a control system can be predicted using game theory, focusing on an autonomous truck platoon interacting with a human-driven car. The interaction is modelled as a hierarchical dynamic game, where the hie, Denna avhandling studerar styrsystem med autonoma beslutsfattare och människor. Vi formaliserar och beräknar styrlagar av låg komplexitet med tillämpningar på storskaliga system samt föreslår modeller för mänsklig interaktion som kan användas av regulatorer för att beräkna interaktionsmedvetna beslut. I den första delen av denna avhandling studerar vi komplexitet-medveten beslutsfattning, där vi formaliserar styrlagars komplexitet samt konstruerar algoritmer som beräknar styrlagar med låg komplexitet. Mer precist, först studerar vi storskaliga system givna av hierarkiska finita tillståndsmaskiner (HFSMs) och presenterar en planeringsalgoritm för sådana system som utnyttjar hierarkin för att beräkna optimala styrlagar effektivt. Algoritmen kan också lätt hantera förändringar i systemet. Vi bevisar dessa egenskaper och utför simuleringar på HFSMs med upp till 2 miljoner tillstånd, inklusive en robot-applikation, där vår algorithm överträffar både Dijkstra's algoritm och så kallade Contraction Hierarchies. För det andra så presenterar vi ett planeringsobjektiv för finita tillståndsmaskiner som ger en explicit avvägning mellan ett styrlags prestanda och komplexitet. Vi använder Kolmogorovkomplexitet då den fångar den ultimata komprimeringen av ett objekt i en universell Turing-maskin. Vi bevisar att detta objektiv är icke-trivial att optimera över i avseendet att dynamisk programming är omöjligt att utföra. Vi presenterar två algoritmer som beräknar styrlagar med låg komplexitet och evaluerar våra algoritmer på ett enkelt navigationsproblem där vi erhåller styrlagar av låg komplexitet som instämmer med intuition. I den andra delen av denna avhandling behandlar vi reglersystem där en människa interagerar med systemet och studerar hur mänskligt beslutsfattande i sådana system kan förutspås. Först studerar vi hur interaktionen mellan en maskin och en människa i ett reglersystem can förutspås med hjälp av spelteori, med fokus på en självkörande lastbilskonvoj som interagera, QC 20230523
- Published
- 2023
65. Complexity-aware Decision-making with Applications to Large-scale and Human-in-the-loop Systems
- Abstract
This thesis considers control systems governed by autonomous decision-makers and humans. We formalise and compute low-complex control policies with applications to large-scale systems, and propose human interaction models for controllers to compute interaction-aware decisions. In the first part of the thesis, we consider complexity-aware decision-making, formalising the complexity of control policies and constructing algorithms that compute low-complexity control policies. More precisely, first, we consider large-scale control systems given by hierarchical finite state machines (HFSMs) and present a planning algorithm for such systems that exploits the hierarchy to compute optimal policies efficiently. The algorithm can also handle changes in the system with ease. We prove these properties and conduct simulations on HFSMs with up to 2 million states, including a robot application, where our algorithm outperforms both Dijkstra's algorithm and Contraction Hierarchies. Second, we present a planning objective for control systems modelled as finite state machines yielding an explicit trade-off between a policy's performance and complexity. We consider Kolmogorov complexity since it captures the ultimate compression of an object on a universal Turing machine. We prove that this trade-off is hard to optimise in the sense that dynamic programming is infeasible. Nonetheless, we present two heuristic algorithms obtaining low-complexity policies and evaluate the algorithms on a simple navigation task for a mobile robot, where we obtain low-complexity policies that concur with intuition. In the second part of the thesis, we consider human-in-the-loop systems and predict human decision-making in such systems. First, we look at how the interaction between a robot and a human in a control system can be predicted using game theory, focusing on an autonomous truck platoon interacting with a human-driven car. The interaction is modelled as a hierarchical dynamic game, where the hie, Denna avhandling studerar styrsystem med autonoma beslutsfattare och människor. Vi formaliserar och beräknar styrlagar av låg komplexitet med tillämpningar på storskaliga system samt föreslår modeller för mänsklig interaktion som kan användas av regulatorer för att beräkna interaktionsmedvetna beslut. I den första delen av denna avhandling studerar vi komplexitet-medveten beslutsfattning, där vi formaliserar styrlagars komplexitet samt konstruerar algoritmer som beräknar styrlagar med låg komplexitet. Mer precist, först studerar vi storskaliga system givna av hierarkiska finita tillståndsmaskiner (HFSMs) och presenterar en planeringsalgoritm för sådana system som utnyttjar hierarkin för att beräkna optimala styrlagar effektivt. Algoritmen kan också lätt hantera förändringar i systemet. Vi bevisar dessa egenskaper och utför simuleringar på HFSMs med upp till 2 miljoner tillstånd, inklusive en robot-applikation, där vår algorithm överträffar både Dijkstra's algoritm och så kallade Contraction Hierarchies. För det andra så presenterar vi ett planeringsobjektiv för finita tillståndsmaskiner som ger en explicit avvägning mellan ett styrlags prestanda och komplexitet. Vi använder Kolmogorovkomplexitet då den fångar den ultimata komprimeringen av ett objekt i en universell Turing-maskin. Vi bevisar att detta objektiv är icke-trivial att optimera över i avseendet att dynamisk programming är omöjligt att utföra. Vi presenterar två algoritmer som beräknar styrlagar med låg komplexitet och evaluerar våra algoritmer på ett enkelt navigationsproblem där vi erhåller styrlagar av låg komplexitet som instämmer med intuition. I den andra delen av denna avhandling behandlar vi reglersystem där en människa interagerar med systemet och studerar hur mänskligt beslutsfattande i sådana system kan förutspås. Först studerar vi hur interaktionen mellan en maskin och en människa i ett reglersystem can förutspås med hjälp av spelteori, med fokus på en självkörande lastbilskonvoj som interagera, QC 20230523
- Published
- 2023
66. Parallel decomposition and concurrent satisfaction for heterogeneous multi-robot task and motion planning under temporal logic specifications
- Author
-
Zheng, Huanfei and Wang, Yue
- Published
- 2022
- Full Text
- View/download PDF
67. Composite Neutrosophic Finite Automata.
- Author
-
Kavikumar, J., Nagarajan, D., Tiwari, S. P., Broumi, Said, and Smarandache, Florentin
- Subjects
- *
FINITE state machines , *COMPUTER simulation , *SET theory , *MACHINE theory , *MATHEMATICAL models - Abstract
The idea behind the neutrosophic set is we can connect the concept by dynamics of opposite interacts and its neutral that are uncertain and get common parts. Automata theory is beneficial to solve computational complexity problem and also it is an in uential mathematical modeling tool in computer science. Inspired by the concepts of neutrosophic sets and automata theory, here, we are introducing and discussing the algebraic concept of neutrosophic finite automata based on the paper [10]. Generally, composite machines can be achieved by the output of the one machine that will be used as input for another machines. This paper introduced the concept of composite automata under the environment of the neutrosophic set and also examined the box function between the composite neutrosophic finite automata. [ABSTRACT FROM AUTHOR]
- Published
- 2020
68. Automated Deduction – CADE 29
- Author
-
Pientka, Brigitte and Tinelli, Cesare
- Subjects
artificial intelligence ,automata theory ,Boolean functions ,formal languages ,formal logic ,model checking ,software engineering ,automated theorem proving ,software verification ,logic programming ,automated reasoning ,automated deduction ,propositional satisfiability ,constraint solving ,computer algebra ,satisfiability modulo theories ,bic Book Industry Communication::U Computing & information technology::UY Computer science::UYQ Artificial intelligence ,bic Book Industry Communication::U Computing & information technology::UY Computer science::UYA Mathematical theory of computation ,bic Book Industry Communication::U Computing & information technology::UM Computer programming / software development ,bic Book Industry Communication::U Computing & information technology::UM Computer programming / software development::UMZ Software Engineering - Abstract
This open access book constitutes the proceedings of the 29th International Conference on Automated Deduction, CADE 29, which took place in Rome, Italy, during July 2023. The 28 full papers and 5 short papers presented were carefully reviewed and selected from 77 submissions. CADE is the major forum for the presentation of research in all aspects of automated deduction, including foundations, applications, implementations, and practical experience. The papers are organized in the following topics: Logical foundations; theory and principles; implementation and application; ATP and AI; and system descriptions.
- Published
- 2023
- Full Text
- View/download PDF
69. From Automata to Multiautomata via Theory of Hypercompositional Structures
- Author
-
Štěpán Křehlík, Michal Novák, and Jana Vyroubalová
- Subjects
automata theory ,hypergroups ,quasi-automata ,quasi-multiautomata ,semiautomata ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2021
- Full Text
- View/download PDF
70. Additive Number Theory via Approximation by Regular Languages.
- Author
-
Bell, Jason, Lidbetter, Thomas F., and Shallit, Jeffrey
- Subjects
- *
NUMBER theory , *APPROXIMATION theory , *FORMAL languages , *PHILOSOPHY of language , *NATURAL numbers - Abstract
We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number > 2 5 is the sum of at most three natural numbers whose base- 2 representation has an equal number of 0 's and 1 's. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
71. Towards a tropical automaton product minimizing global completion times.
- Author
-
Quintero, Karla, Aguilar, Jose, Niel, Eric, and Pietrac, Laurent
- Abstract
The main contribution of this paper is oriented towards system modeling with resource conflicts, in which a set of tasks must be completed at the earliest. Mutual exclusion between tasks with underlying resource conflicts is modeled as subsystems through local tropical automata. Parallel task execution is explored through a new framework for a synchronous product of tropical automata directly minimizing the global completion time of a set of tasks. A dater-based analysis is proposed to determine an optimal qualitative schedule and relies on proposed definitions of global, private, and synchronizing daters. This approach drastically narrows the solution spectrum, and allows finding the optimal task schedule. The approach is applied to a flow network as a case study, but can be applied to systems of different nature. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
72. Additive Number Theory via Automata Theory.
- Author
-
Rajasekaran, Aayush, Shallit, Jeffrey, and Smith, Tim
- Subjects
- *
NUMBER theory , *MACHINE theory , *ROBOTS , *FIRST-order logic , *FINITE state machines , *NATURAL numbers - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
73. State complexity of combined operations involving catenation and binary Boolean operations: Beyond the Brzozowski conjectures.
- Author
-
Caron, Pascal, Luque, Jean-Gabriel, and Patrou, Bruno
- Subjects
- *
BINARY operations , *LOGICAL prediction , *BINARY number system - Abstract
We exhaustively investigate possible combinations of a Boolean operation together with a catenation. In many cases we prove and improve some conjectures by Brzozowski. For each family of operations, we endeavour to provide a common witness with a small size alphabet. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
74. Computing Simple Quantifiers
- Author
-
Szymanik, Jakub, McNally, Louise, Series editor, Sharvit, Yael, Series editor, Szabo, Zoltan, Series editor, and Szymanik, Jakub
- Published
- 2016
- Full Text
- View/download PDF
75. Temporal logics with language parameters.
- Author
-
Gutsfeld, Jens Oliver, Müller-Olm, Markus, and Dielitz, Christian
- Subjects
- *
FORMAL languages , *LOGIC , *FOREIGN language education , *LANGUAGE & languages - Abstract
We develop a generic framework to extend the logics LTL, CTL+ and CTL⁎ by automata-based connectives from formal language classes and analyse this framework with regard to regular languages, visibly pushdown languages, deterministic and non-deterministic context-free languages. More precisely, we consider how the use of different automata classes changes the expressive power of the logics and provide algorithms for the satisfiability and model checking problems induced by the use of different classes of automata. For the model checking problem, we treat not only finite Kripke transition systems, but also visibly pushdown systems and pushdown systems. We provide completeness or undecidability results in all cases and show that the extensions we consider can formulate properties not expressible in classical temporal logics or regular extensions thereof. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
76. Relationships between the Chicken McNugget Problem, Mutations of Brauer Configuration Algebras and the Advanced Encryption Standard
- Author
-
Agustín Moreno Cañadas, Isaías David Marín Gaviria, and Juan David Camacho Vega
- Subjects
advanced encryption standard (AES) ,automata theory ,Brauer configuration algebra ,chicken mcnugget problem (CMP) ,cryptography ,Diophantine equation ,Mathematics ,QA1-939 - Abstract
Mutations on Brauer configurations are introduced and associated with some suitable automata to solve generalizations of the Chicken McNugget problem. Additionally, based on marked order polytopes, the new Diophantine equations called Gelfand–Tsetlin equations are also solved. The approach allows algebraic descriptions of some properties of the AES key schedule via some Brauer configuration algebras and suitable non-deterministic finite automata (NFA).
- Published
- 2021
- Full Text
- View/download PDF
77. Solomon Marcus Contributions to Theoretical Computer Science and Applications.
- Author
-
Calude, Cristian S. and Păun, Gheorghe
- Subjects
- *
COMPUTER science , *NATURAL computation , *MATHEMATICAL linguistics , *MACHINE theory - Abstract
Solomon Marcus (1925-2016) was one of the founders of the Romanian theoretical computer science. His pioneering contributions to automata and formal language theories, mathematical linguistics and natural computing have been widely recognised internationally. In this paper we briefly present his publications in theoretical computer science and related areas, which consist in almost ninety papers. Finally we present a selection of ten Marcus books in these areas. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
78. A Framework for Data-Driven Automata Design
- Author
-
Zhang, Yuanrui, Chen, Yixiang, Ma, Yujing, Diniz Junqueira Barbosa, Simone, Series editor, Chen, Phoebe, Series editor, Du, Xiaoyong, Series editor, Filipe, Joaquim, Series editor, Kara, Orhun, Series editor, Kotenko, Igor, Series editor, Liu, Ting, Series editor, Sivalingam, Krishna M., Series editor, Washio, Takashi, Series editor, Liu, Lin, editor, and Aoyama, Mikio, editor
- Published
- 2015
- Full Text
- View/download PDF
79. A Formal Framework for Program Anomaly Detection
- Author
-
Shu, Xiaokui, Yao, Danfeng (Daphne), Ryder, Barbara G., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bos, Herbert, editor, Monrose, Fabian, editor, and Blanc, Gregory, editor
- Published
- 2015
- Full Text
- View/download PDF
80. Solomon Marcus Contributions to Theoretical Computer Science and Applications
- Author
-
Cristian S. Calude and Gheorghe Păun
- Subjects
automata theory ,formal language theory ,bio-informatics ,recursive function theory ,Mathematics ,QA1-939 - Abstract
Solomon Marcus (1925–2016) was one of the founders of the Romanian theoretical computer science. His pioneering contributions to automata and formal language theories, mathematical linguistics and natural computing have been widely recognised internationally. In this paper we briefly present his publications in theoretical computer science and related areas, which consist in almost ninety papers. Finally we present a selection of ten Marcus books in these areas.
- Published
- 2021
- Full Text
- View/download PDF
81. Efficient Implementation for Deterministic Finite Tree Automata Minimization
- Author
-
Younes Guellouma and Hadda Cherroun
- Subjects
automata theory ,minimization ,trees ,asymptotic complexity ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
We address the problem of deterministic finite tree automata (DFTA) minimization. We describe a new alternative to implement both standard and incremental tree automata minimization using a well-defined graph representing the automaton to be minimized. We show that the asymptotic complexity of the standard implementation is linearithmic and the incremental one is O(n3 log(n)) where n is the DFTA size.
- Published
- 2016
- Full Text
- View/download PDF
82. Modelling of a virtual power plant using hybrid automata
- Author
-
Chaudhry Jibran Javaid, Adib Allahham, Damian Giaouris, Simon Blake, and Phil Taylor
- Subjects
automata theory ,hybrid power systems ,power generation control ,power plants ,control system synthesis ,virtual power plant ,hybrid automata ,VPP ,hybrid power system ,distributed resources ,local loads ,discrete variables ,continuous variables ,advanced control schemes ,distributed assets ,actual power plant ,modelling tools ,research farm ,Newcastle University ,control design ,Engineering (General). Civil engineering (General) ,TA1-2040 - Abstract
Virtual power plant (VPP) is a hybrid power system with a mesh of distributed resources, local loads and storage with both discrete and continuous variables involved. Control of such system requires advanced control schemes to make distributed assets act together to mimic an actual power plant. Previously, to study the behaviour of such systems, complex algorithms and modelling tools have been used but this paper proposes the use of Hybrid Automata (HA) as a convenient tool to model these systems. To demonstrate this, HA is used to model a VPP for a research farm owned by Newcastle University as a first step to design the control for the system.
- Published
- 2019
- Full Text
- View/download PDF
83. An Algebraic Approach to Vectorial Programs
- Author
-
Paperman, Charles, Salvati, Sylvain, Soyez-Martin, Claire, Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Vectorisation ,Theory of computation → Formal languages and automata theory ,[INFO]Computer Science [cs] ,Semigroups ,Automata theory - Abstract
Vectorial programming, the combination of SIMD instructions with usual processor instructions, is known to speed-up many standard algorithms. Simple regular languages have benefited from this technology. This paper is a first step towards pushing these benefits further. We take advantage of the inner algebraic structure of regular languages and produce high level representations of efficient vectorial programs that recognize certain classes of regular languages. As a technical ingredient, we establish equivalences between classes of vectorial circuits and logical formalisms, namely unary temporal logic and first order logic. The main result is the construction of compilation procedures that turns syntactic semigroups into vectorial circuits. The circuits we obtain are small in that they improve known upper-bounds on representations of automata within the logical formalisms. The gain is mostly due to a careful sharing of sub-formulas based on algebraic tools., LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 51:1-51:23
- Published
- 2023
- Full Text
- View/download PDF
84. Complexity-aware Decision-making with Applications to Large-scale and Human-in-the-loop Systems
- Author
-
Stefansson, Elis
- Subjects
Complexity-aware Decision-making ,Large-scale Systems ,Game Theory ,Automata Theory ,Optimal Control ,Reglerteknik ,Kolmogorov Complexity ,Automatic Control ,Autonomous vehicles ,Hierarchical Finite State Machines ,Human-in-the-loop ,Human Decision-making ,Control Engineering - Abstract
This thesis considers control systems governed by autonomous decision-makers and humans. We formalise and compute low-complex control policies with applications to large-scale systems, and propose human interaction models for controllers to compute interaction-aware decisions. In the first part of the thesis, we consider complexity-aware decision-making, formalising the complexity of control policies and constructing algorithms that compute low-complexity control policies. More precisely, first, we consider large-scale control systems given by hierarchical finite state machines (HFSMs) and present a planning algorithm for such systems that exploits the hierarchy to compute optimal policies efficiently. The algorithm can also handle changes in the system with ease. We prove these properties and conduct simulations on HFSMs with up to 2 million states, including a robot application, where our algorithm outperforms both Dijkstra's algorithm and Contraction Hierarchies. Second, we present a planning objective for control systems modelled as finite state machines yielding an explicit trade-off between a policy's performance and complexity. We consider Kolmogorov complexity since it captures the ultimate compression of an object on a universal Turing machine. We prove that this trade-off is hard to optimise in the sense that dynamic programming is infeasible. Nonetheless, we present two heuristic algorithms obtaining low-complexity policies and evaluate the algorithms on a simple navigation task for a mobile robot, where we obtain low-complexity policies that concur with intuition. In the second part of the thesis, we consider human-in-the-loop systems and predict human decision-making in such systems. First, we look at how the interaction between a robot and a human in a control system can be predicted using game theory, focusing on an autonomous truck platoon interacting with a human-driven car. The interaction is modelled as a hierarchical dynamic game, where the hierarchical decomposition is temporal with a high-fidelity tactical horizon predicting immediate interactions and a low-fidelity strategic horizon estimating long-term behaviour. The game enables feasible computations validated through simulations yielding situation-aware behaviour with natural and safe interactions. Second, we seek models to explain human decision-making, focusing on driver overtaking scenarios. The overtaking problem is formalised as a decision problem with perceptual uncertainty. We propose and numerically analyse risk-agnostic and risk-aware decision models, judging if an overtaking is desirable. We show how a driver's decision time and confidence level can be characterised through two model parameters, which collectively represent human risk-taking behaviour. We detail an experimental testbed for evaluating the decision-making process in the overtaking scenario and present some preliminary experimental results from two human drivers. Denna avhandling studerar styrsystem med autonoma beslutsfattare och människor. Vi formaliserar och beräknar styrlagar av låg komplexitet med tillämpningar på storskaliga system samt föreslår modeller för mänsklig interaktion som kan användas av regulatorer för att beräkna interaktionsmedvetna beslut. I den första delen av denna avhandling studerar vi komplexitet-medveten beslutsfattning, där vi formaliserar styrlagars komplexitet samt konstruerar algoritmer som beräknar styrlagar med låg komplexitet. Mer precist, först studerar vi storskaliga system givna av hierarkiska finita tillståndsmaskiner (HFSMs) och presenterar en planeringsalgoritm för sådana system som utnyttjar hierarkin för att beräkna optimala styrlagar effektivt. Algoritmen kan också lätt hantera förändringar i systemet. Vi bevisar dessa egenskaper och utför simuleringar på HFSMs med upp till 2 miljoner tillstånd, inklusive en robot-applikation, där vår algorithm överträffar både Dijkstra's algoritm och så kallade Contraction Hierarchies. För det andra så presenterar vi ett planeringsobjektiv för finita tillståndsmaskiner som ger en explicit avvägning mellan ett styrlags prestanda och komplexitet. Vi använder Kolmogorovkomplexitet då den fångar den ultimata komprimeringen av ett objekt i en universell Turing-maskin. Vi bevisar att detta objektiv är icke-trivial att optimera över i avseendet att dynamisk programming är omöjligt att utföra. Vi presenterar två algoritmer som beräknar styrlagar med låg komplexitet och evaluerar våra algoritmer på ett enkelt navigationsproblem där vi erhåller styrlagar av låg komplexitet som instämmer med intuition. I den andra delen av denna avhandling behandlar vi reglersystem där en människa interagerar med systemet och studerar hur mänskligt beslutsfattande i sådana system kan förutspås. Först studerar vi hur interaktionen mellan en maskin och en människa i ett reglersystem can förutspås med hjälp av spelteori, med fokus på en självkörande lastbilskonvoj som interagerar med en mänskligt styrd bil. Interaktionen är modellerad som ett hierarkiskt dynamiskt spel, där den hierarkiska indelningen är tidsmässig med en högupplöst taktil horisont som förutspår omedelbara interaktioner samt en lågupplöst strategisk horisont som estimerar långtgående interaktioner. Indelning möjliggör beräkningar som vi validerar via simuleringar där vi får situations-medvetet beteende med naturliga och säkra interaktioner. För det andra söker vi en model med få parametrar som förklarar mänskligt beteende där vi fokuserar på omkörningar. Vi formaliserar omkörningsproblemet som ett beslutfattningsproblem med perceptuell osäkerhet. Vi presenterar och analyserar numeriskt risk-agnostiska och risk-medvetna beslutsmodeller som avväger om en omkörning är önskvärd. Vi visar hur en förares beslutstid och konfidensnivå kan karakteriserar via två modellparametrar som tillsammans representerar mänskligt risk-beteende. Vi beskriver en experimentell testbädd och presentar preliminära resultat från två mänskliga förare. QC 20230523
- Published
- 2023
85. Sequences of Groups, Hypergroups and Automata of Linear Ordinary Differential Operators
- Author
-
Jan Chvalina, Michal Novák, Bedřich Smetana, and David Staněk
- Subjects
hyperstructure theory ,linear differential operators ,ODE ,automata theory ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2021
- Full Text
- View/download PDF
86. Posture labeling based gesture classification for Turkish sign language using depth values
- Author
-
Ediz Saykol, Halit Talha Türe, Ahmet Mert Sirvanci, and Mert Turan
- Published
- 2016
- Full Text
- View/download PDF
87. Automata Simulator: A mobile app to teach theory of computation.
- Author
-
Singh, Tuhina, Afreen, Simra, Chakraborty, Pinaki, Raj, Rashmi, Yadav, Savita, and Jain, Dipika
- Subjects
MACHINE theory ,MOBILE apps ,LEARNING ,CONCEPT learning - Abstract
We developed a mobile app named Automata Simulator to simulate different types of automata and used it to teach the course on theory of computation. The students used the app to design and simulate automata during the lectures. The students also used a more sophisticated desktop application, JFLAP, to study advanced concepts related to automata theory after the lectures. An analysis of the examination results revealed that this approach helped the students to learn the concepts better and score 1% more marks. Moreover, a strong correlation between the marks obtained by the students for questions related to designing of automata and their total score was identified. In a survey conducted at the end of the semester, the students said that it was difficult to use two tools for learning the same concepts. However, they also felt that the combination of the two tools made the course more interactive and contributed positively in the process of learning. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
88. Modelling of a virtual power plant using hybrid automata.
- Author
-
Javaid, Chaudhry Jibran, Allahham, Adib, Giaouris, Damian, Blake, Simon, and Taylor, Phil
- Subjects
HYBRID power systems ,POWER plant design & construction ,ENERGY storage ,ELECTRIC power production ,MATHEMATICAL models - Abstract
Virtual power plant (VPP) is a hybrid power system with a mesh of distributed resources, local loads and storage with both discrete and continuous variables involved. Control of such system requires advanced control schemes to make distributed assets act together to mimic an actual power plant. Previously, to study the behaviour of such systems, complex algorithms and modelling tools have been used but this paper proposes the use of Hybrid Automata (HA) as a convenient tool to model these systems. To demonstrate this, HA is used to model a VPP for a research farm owned by Newcastle University as a first step to design the control for the system. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
89. Randomness of formal languages via automatic martingales.
- Author
-
Moldagaliyev, Birzhan
- Subjects
- *
FORMAL languages , *MARTINGALES (Mathematics) , *LANGUAGE & languages , *ALGORITHMIC randomness , *CAPITAL gains - Abstract
We define a notion of randomness for individual and collections of formal languages based on automatic martingales acting on sequences of words from some underlying domain. An automatic martingale bets if the incoming word belongs to the target language or not. Then randomness of both single languages and collections of languages is defined as a failure of automatic martingale to gain an unbounded capital by betting on the target language according to an incoming sequence of words, or a text. The randomness of formal languages turned out to be heavily dependent on the text. For very general classes of texts, any nonregular language happens to be random when considered individually. As for collections of languages, very general classes of texts permits nonrandomness of automatic families of languages only. On the other hand, an arbitrary computable language is shown to be nonrandom under certain dynamic texts. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
90. FUZZY SUBSETS OF THE PHENOTYPES OF F2-OFFSPRING.
- Author
-
Al-Tahan, Madeleine and Davvaz, Bijan
- Subjects
- *
FUZZY sets , *SEQUENCE spaces , *PHENOTYPES , *HYPERGROUPS - Abstract
This paper presents a connection between fuzzy sets, biological inheritance and hyperstructures in which we consider the set of phenotypes of the second generation F2 in different types of inheritance, define fuzzy subsets of it and construct a sequence of join spaces associated to each of its types. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
91. Event‐triggered hybrid control strategy based on hybrid automata and decision tree for microgrid.
- Author
-
Dou, Chunxia, Teng, Shengqi, Zhang, Tengfei, Zhang, Bo, and Ma, Kai
- Abstract
The event‐triggered hybrid control is proposed in this study to realise multi‐model switching when the microgrid system is operating in the island mode. The hybrid control includes decentralised control strategy and coordinated control strategy. Firstly, control commands in the hybrid control strategy are triggered by the event triggering mechanism including trigger events and trigger conditions. When a trigger condition is met, the corresponding event is triggered to execute the corresponding control command. Secondly, the microgrid system is divided into an upper control layer and a lower execution layer by using the multi‐agent system theory. For the upper control layer, a coordinated control strategy based on decision tree algorithm is designed, which can not only issue switching control commands to the lower execution layer, but also reduce the number of switching, improve system stability, and enrich the control strategy. For the lower execution layer, a decentralised control strategy is designed to realise distributed operation of the underlying units. Finally, the model of hybrid automata of each unit is established to ensure the smooth switching of working modes of each unit. The simulation results verify the effectiveness of the event‐triggered hybrid control strategy for controlling the microgrid. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
92. Detection of nucleotide sequences capable of forming non-canonical DNA structures: Application of automata theory.
- Author
-
Yurushkin, M.V., Gervich, L.R., Bachurin, S.S., and Kletskii, M.E.
- Subjects
- *
NUCLEOTIDE sequence , *DNA structure , *SINGLE nucleotide polymorphisms , *THEORY-practice relationship , *MOLECULAR biologists , *GENETIC disorders - Abstract
• Nucleotide sequences capable to form combinations of DNA non-canonical structures were detected. • Special software for molecular biologist was developed. • Minimal length of nucleotide sequences with structural polymorphism was revealed. In this study, we develop a program that allows us to reveal DNA receptors, i.e. nucleotide sequences that may form more than one non-canonical structure. The data obtained may be analysed either experimentally or using DNA banks, and refers to the coding, non-coding or promotor region of the gene. These results provide a better understanding of the role that non-canonical structures play in pathological modifications of the genetic apparatus, resulting in tumour formation or inherited disease. They also reveal the effect of single nucleotide polymorphisms on gene expression, indicate so-called "risk regions" in which the substitution of a single nucleotide may lead to increased formation of non-canonical structures, and elucidate the epigenetic mechanisms of microorganism adaptation. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
93. Equational properties of fixed-point operations in cartesian categories: An overview.
- Author
-
Ésik, Z
- Subjects
MONOTONIC functions ,BINARY operations ,CONTINUOUS functions ,FIXED point theory ,ADDITION (Mathematics) ,MATHEMATICAL equivalence ,ANALYTIC geometry - Abstract
Several fixed-point models share the equational properties of iteration theories, or iteration categories, which are cartesian categories equipped with a fixed point or dagger operation subject to certain axioms. After discussing some of the basic models, we provide equational bases for iteration categories and offer an analysis of the axioms. Although iteration categories have no finite base for their identities, there exist finitely based implicational theories that capture their equational theory. We exhibit several such systems. Then we enrich iteration categories with an additive structure and exhibit interesting cases where the interaction between the iteration category structure and the additive structure can be captured by a finite number of identities. This includes the iteration category of monotonic or continuous functions over complete lattices equipped with the least fixed-point operation and the binary supremum operation as addition, the categories of simulation, bisimulation, or language equivalence classes of processes, context-free languages, and others. Finally, we exhibit a finite equational system involving residuals, which is sound and complete for monotonic or continuous functions over complete lattices in the sense that it proves all of their identities involving the operations and constants of cartesian categories, the least fixed-point operation and binary supremum, but not involving residuals. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
94. Algorithmic and Complexity Aspects of Path Computation in Multi-Layer Networks.
- Author
-
Lamali, Mohamed Lamine, Fergani, Nasreddine, and Cohen, Johanne
- Subjects
ROUTING (Computer network management) ,SOFTWARE-defined networking - Abstract
Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to a suboptimal use of the network resources and to additional operational costs. However, some routers are able to encapsulate, decapsulate, and convert protocols, and act as a liaison between these layers. A unified control plane would be useful to optimize the use of the network resources and to automate the routing configurations. Software-defined networking-based architectures offer an opportunity to design such a control plane. One of the most important problems to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem, as they do not take into account encapsulations and conversions of protocols. In this paper, we propose algorithms to solve this problem and study several cases. If there is no bandwidth constraint, we propose a polynomial algorithm that computes the optimal path. We also give lower and upper bounds on the optimal path length. On the other hand, we show that the problem is $\mathsf {NP}$ -hard if there is a bandwidth constraint (or other quality-of-service parameters), even if there is only two protocols and in a symmetric graph. We study the complexity and the scalability of our algorithms and evaluate their performances on real and random topologies. The results show that they are faster than the previous ones proposed in the literature. These algorithms can also have important applications in automatic tunneling. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
95. Classes of languages generated by the Kleene star of a word.
- Author
-
Daviaud, Laure and Paperman, Charles
- Subjects
- *
LANGUAGE & languages , *KLEENE algebra , *ALGEBRAIC logic , *LATTICE dynamics , *BOOLEAN algebra - Abstract
Abstract In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form u ⁎ , where u is a word. We provide effective equational characterisations of these classes, i.e. one can decide using our descriptions whether a given regular language belongs or not to each of them. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
96. From decidability to undecidability by considering regular sets of instances
- Author
-
Petra Wolf
- Subjects
FOS: Computer and information sciences ,Mathematics::Commutative Algebra ,General Computer Science ,Formal Languages and Automata Theory (cs.FL) ,Intersection (set theory) ,Boundary (topology) ,Computer Science - Formal Languages and Automata Theory ,Field (mathematics) ,Theoretical Computer Science ,Undecidable problem ,Decidability ,Combinatorics ,Set (abstract data type) ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Automata theory ,Computer Science::Formal Languages and Automata Theory ,Mathematics ,PSPACE - Abstract
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.
- Published
- 2022
97. A Survey on String Constraint Solving
- Author
-
AmadiniRoberto and Amadini, Roberto
- Subjects
TheoryofComputation_MISCELLANEOUS ,FOS: Computer and information sciences ,General Computer Science ,Computer Science - Artificial Intelligence ,Formal Languages and Automata Theory (cs.FL) ,Computer science ,String (computer science) ,Computer Science - Formal Languages and Automata Theory ,Theoretical Computer Science ,Algebra ,Constraint (information theory) ,High Energy Physics::Theory ,Artificial Intelligence (cs.AI) ,Satisfiability modulo theories ,Constraint programming ,Automata theory ,String Solving, String Analysis, Program Analysis, Satisfiability Modulo Theories, Constraint Programming ,Software analysis pattern - Abstract
String constraint solving refers to solving combinatorial problems involving constraints over string variables. String solving approaches have become popular over the last years given the massive use of strings in different application domains like formal analysis, automated testing, database query processing, and cybersecurity. This paper reports a comprehensive survey on string constraint solving by exploring the large number of approaches that have been proposed over the last decades to solve string constraints., Comment: Under consideration for "ACM Computing Surveys" journal
- Published
- 2021
98. До теорії синтезу мінімальних схем систем управління гідро- і певмоприводів
- Author
-
Cherkashenko, Mikhaylo
- Subjects
математична модель ,теорія автоматів ,рівняння ,теорія графів ,загальна алгебра ,graph theory ,equations ,minimal scheme ,мінімальна схема ,general algebra ,automata theory ,mathematical model - Abstract
Showed the strict compliance of the scientific direction "Synthesis of minimum control schemes of hydraulic and pneumatic drive systems" developed by the author with the point of view of general algebra, algebra of logic, graph theory and automata theory. The synthesis of the minimum graph of operations, which is a mathematical model of the control system, has been proved. The legitimacy of the methods of undivided decomposition of equations describing the scheme of the control system has been proved. The control system is considered as a cyclic Moore finite automaton. By a cyclic automaton (CA) we will understand the mathematical model of a device designed to control cyclic processes, which are a set of technological operations performed in a certain sequence. In this regard, the automaton at each clock necessarily passes into some new state, and for a finite number of cycles the target reaches any state, and its graph contains a contour, covering all states. In general, the CA may contain several circuits, so that each circuit is interpreted either as one of the possible sequences of technological operations due to the corresponding mode of operation, or as an independent and simultaneous execution of a number of sets of technological operations. A sequential decomposition of the CA is presented in order to represent it by the sequential operation of automata with one internal state. Such a consideration of the function of transitions will naturally lead to a decrease in the number of elements in the implementation of the CA. The study will be subjected to the CA, the graph of which consists of a single circuit, since the results obtained are easily generalized to multi-circuit CA. Obtaining a breakdown of the states of a cyclic automaton in the manner indicated above is performed directly according to any automaton description without any additional calculations, tables and other constructions., Showed the strict compliance of the scientific direction "Synthesis of minimum control schemes of hydraulic and pneumatic drive systems" developed by the author with the point of view of general algebra, algebra of logic, graph theory and automata theory. The synthesis of the minimum graph of operations, which is a mathematical model of the control system, has been proved. The legitimacy of the methods of undivided decomposition of equations describing the scheme of the control system has been proved. The control system is considered as a cyclic Moore finite automaton. By a cyclic automaton (CA) we will understand the mathematical model of a device designed to control cyclic processes, which are a set of technological operations performed in a certain sequence. In this regard, the automaton at each clock necessarily passes into some new state, and for a finite number of cycles the target reaches any state, and its graph contains a contour, covering all states. In general, the CA may contain several circuits, so that each circuit is interpreted either as one of the possible sequences of technological operations due to the corresponding mode of operation, or as anindependent and simultaneous execution of a number of sets of technological operations. A sequential decomposition of the CA is presented in order to represent it by the sequential operation of automata with one internal state. Such a consideration of the function of transitions will naturally lead to a decrease in the number of elements in the implementation of the CA. The study will be subjected to the CA, the graph of which consists of a singlecircuit, since the results obtained are easily generalized to multi-circuit CA. Obtaining a breakdown of the states of a cyclic automaton in the manner indicated above is performed directly according to any automaton description without any additional calculations, tables and other constructions
- Published
- 2022
99. Modelling Consciousness within Mental Monism: An Automata-Theoretic Approach
- Author
-
Peter B. Lloyd
- Subjects
idealism ,consciousness ,Hard Problem ,automata theory ,mental models ,Science ,Astrophysics ,QB460-466 ,Physics ,QC1-999 - Abstract
Models of consciousness are usually developed within physical monist or dualistic frameworks, in which the structure and dynamics of the mind are derived from the workings of the physical brain. Little attention has been given to modelling consciousness within a mental monist framework, deriving the structure and dynamics of the mental world from primitive mental constituents only—with no neural substrate. Mental monism is gaining attention as a candidate solution to Chalmers’ Hard Problem on philosophical grounds, and it is therefore timely to examine possible formal models of consciousness within it. Here, I argue that the austere ontology of mental monism places certain constraints on possible models of consciousness, and propose a minimal set of hypotheses that a model of consciousness (within mental monism) should respect. From those hypotheses, it would be possible to construct many formal models that permit universal computation in the mental world, through cellular automata. We need further hypotheses to define transition rules for particular models, and I propose a transition rule with the unusual property of deep copying in the time dimension.
- Published
- 2020
- Full Text
- View/download PDF
100. n-Ary Cartesian Composition of Multiautomata with Internal Link for Autonomous Control of Lane Shifting
- Author
-
Štěpán Křehlík
- Subjects
hypergroup ,automata theory ,cartesian composition ,autonomous vehicles ,cooperative intelligent transport systems ,Mathematics ,QA1-939 - Abstract
In this paper, which is based on a real-life motivation, we present an algebraic theory of automata and multi-automata. We combine these (multi-)automata using the products introduced by W. Dörfler, where we work with the cartesian composition and we define the internal links among multiautomata by means of the internal links’ matrix. We used the obtained product of n-ary multi-automata as a system that models and controls certain traffic situations (lane shifting) for autonomous vehicles.
- Published
- 2020
- Full Text
- View/download PDF
Catalog
Books, media, physical & digital resources
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.