Log in

Relevant bibliographies by topics / Algebraic automata theory / Journal articles

To see the other types of publications on this topic, follow the link: Algebraic automata theory.

Journal articles on the topic 'Algebraic automata theory'

Author: Grafiati

Published: 1 June 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Algebraic automata theory.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Pal, Priyanka, S. P. Tiwari, and Renu Verma. "Different Operators in Automata Theory Based on Residuated and Co-Residuated Lattices." New Mathematics and Natural Computation 15, no. 01 (December 25, 2018): 169–90. http://dx.doi.org/10.1142/s1793005719500108.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

2

Chilton, Chris, Bengt Jonsson, and Marta Kwiatkowska. "An algebraic theory of interface automata." Theoretical Computer Science 549 (September 2014): 146–74. http://dx.doi.org/10.1016/j.tcs.2014.07.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Cadilhac, Michaël, Andreas Krebs, and Pierre McKenzie. "The Algebraic Theory of Parikh Automata." Theory of Computing Systems 62, no. 5 (November 7, 2017): 1241–68. http://dx.doi.org/10.1007/s00224-017-9817-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

van Heerdt, Gerco, Joshua Moerman, Matteo Sammartino, and Alexandra Silva. "A (co)algebraic theory of succinct automata." Journal of Logical and Algebraic Methods in Programming 105 (June 2019): 112–25. http://dx.doi.org/10.1016/j.jlamp.2019.02.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Novák, Michal, Štepán Křehlík, and Kyriakos Ovaliadis. "Elements of Hyperstructure Theory in UWSN Design and Data Aggregation." Symmetry 11, no. 6 (May 29, 2019): 734. http://dx.doi.org/10.3390/sym11060734.

Full text

Abstract:

In our paper we discuss how elements of algebraic hyperstructure theory can be used in the context of underwater wireless sensor networks (UWSN). We present a mathematical model which makes use of the fact that when deploying nodes or operating the network we, from the mathematical point of view, regard an operation (or a hyperoperation) and a binary relation. In this part of the paper we relate our context to already existing topics of the algebraic hyperstructure theory such as quasi-order hypergroups, E L -hyperstructures, or ordered hyperstructures. Furthermore, we make use of the theory of quasi-automata (or rather, semiautomata) to relate the process of UWSN data aggregation to the existing algebraic theory of quasi-automata and their hyperstructure generalization. We show that the process of data aggregation can be seen as an automaton, or rather its hyperstructure generalization, with states representing stages of the data aggregation process of cluster protocols and describing available/used memory capacity of the network.

APA, Harvard, Vancouver, ISO, and other styles

6

ANTIĆ, CHRISTIAN. "On Cascade Products of Answer Set Programs." Theory and Practice of Logic Programming 14, no. 4-5 (July 2014): 711–23. http://dx.doi.org/10.1017/s1471068414000301.

Full text

Abstract:

AbstractDescribing complex objects by elementary ones is a common strategy in mathematics and science in general. In their seminal 1965 paper, Kenneth Krohn and John Rhodes showed that every finite deterministic automaton can be represented (or “emulated”) by a cascade product of very simple automata. This led to an elegant algebraic theory of automata based on finite semigroups (Krohn-Rhodes Theory). Surprisingly, by relating logic programs and automata, we can show in this paper that the Krohn-Rhodes Theory is applicable in Answer Set Programming (ASP). More precisely, we recast the concept of a cascade product to ASP, and prove that every program can be represented by a product of very simple programs, the reset and standard programs. Roughly, this implies that the reset and standard programs are the basic building blocks of ASP with respect to the cascade product. In a broader sense, this paper is a first step towards an algebraic theory of products and networks of nonmonotonic reasoning systems based on Krohn-Rhodes Theory, aiming at important open issues in ASP and AI in general.

APA, Harvard, Vancouver, ISO, and other styles

7

Derksen, Harm, Emmanuel Jeandel, and Pascal Koiran. "Quantum automata and algebraic groups." Journal of Symbolic Computation 39, no. 3-4 (March 2005): 357–71. http://dx.doi.org/10.1016/j.jsc.2004.11.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ambainis, Andris, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, and Denis Therien. "Algebraic Results on Quantum Automata." Theory of Computing Systems 39, no. 1 (November 29, 2005): 165–88. http://dx.doi.org/10.1007/s00224-005-1263-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Pal, Priyanka, S. P. Tiwari, and J. Kavikumar. "Measure of Operators Associated with Fuzzy Automata." New Mathematics and Natural Computation 16, no. 01 (March 2020): 17–35. http://dx.doi.org/10.1142/s1793005720500027.

Full text

Abstract:

This paper is toward the study of measure of different operators in fuzzy automata theory, which determine the amount of preciseness of given [Formula: see text]-valued subset endowed with an [Formula: see text]-valued preorder induced by [Formula: see text]-valued transition function of an [Formula: see text]-valued automaton. Further, we study the algebraic and topological study of [Formula: see text]-valued automata via different [Formula: see text]-valued operators and on the basis of homomorphism we examine the behavior of operators associated with an [Formula: see text]-valued automaton.

APA, Harvard, Vancouver, ISO, and other styles

10

LE SAEC, BERTRAND, JEAN-ERIC PIN, and PASCAL WEIL. "SEMIGROUPS WITH IDEMPOTENT STABILIZERS AND APPLICATIONS TO AUTOMATA THEORY." International Journal of Algebra and Computation 01, no. 03 (September 1991): 291–314. http://dx.doi.org/10.1142/s0218196791000195.

Full text

Abstract:

Nous prouvons que tout semigroupe fini est quotient d'un semigroupe fini dans lequel les stabilisateurs droits satisfont les identités x = x2 et xy = xyx. Ce resultat a plusieurs consé-quences. Tout d'abord, nous l'utilisons, en même temps qu'un résultat de I. Simon sur les congruences de chemins, pour obtenir une preuve purement algébrique d'un théorème profond de McNaughton sur les mots infinis. Puis, nous donnons une preuve algébrique d'un théorème de Brown sur des conditions de finitude pour les semigroupes. We show that every finite semigroup is a quotient of a finite semigroup in which every right stabilizer satisfies the identities x = x2 and xy = xyx. This result has several consequences. We first use it together with a result of I. Simon on congruences on paths to obtain a purely algebraic proof of a deep theorem of McNaughton on infinite words. Next, we give an algebraic proof of a theorem of Brown on a finiteness condition for semigroups.

APA, Harvard, Vancouver, ISO, and other styles

11

Kalampakas, Antonios. "Graph Automata and Graph Colorability." European Journal of Pure and Applied Mathematics 16, no. 1 (January 29, 2023): 112–20. http://dx.doi.org/10.29020/nybg.ejpam.v16i1.4629.

Full text

Abstract:

Automata recognizing graphs can be constructed by employing the algebraic structure of graphoids. For the construction of a graph automaton, the relations over the Kleene star of the state set must constitute a graphoid. Hence different kinds of graphoids produce graph automata with diverse operation and recognition capacity. In this paper we show that graph colorability is recognized by automata operating over the simplest possible abelian graphoid.

APA, Harvard, Vancouver, ISO, and other styles

12

Kuich, Werner. "Pushdown Tree Automata, Algebraic Tree Systems, and Algebraic Tree Series." Information and Computation 165, no. 1 (February 2001): 69–99. http://dx.doi.org/10.1006/inco.2000.2908.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Podlovchenko, R. I. "Finite state automata in the theory of algebraic program schemata." Proceedings of the Institute for System Programming of the RAS 27, no. 2 (2015): 161–72. http://dx.doi.org/10.15514/ispras-2015-27(2)-10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Kedlaya, Kiran S. "Finite automata and algebraic extensions of function fields." Journal de Théorie des Nombres de Bordeaux 18, no. 2 (2006): 379–420. http://dx.doi.org/10.5802/jtnb.551.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Křehlík, Štěpán. "n-Ary Cartesian Composition of Multiautomata with Internal Link for Autonomous Control of Lane Shifting." Mathematics 8, no. 5 (May 21, 2020): 835. http://dx.doi.org/10.3390/math8050835.

Full text

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.

APA, Harvard, Vancouver, ISO, and other styles

16

Kim, S. H., and N. P. Suh. "Mathematical Foundations for Manufacturing." Journal of Engineering for Industry 109, no. 3 (August 1, 1987): 213–18. http://dx.doi.org/10.1115/1.3187121.

Full text

Abstract:

For the field of manufacturing to become a science, it is necessary to develop general mathematical descriptions for the analysis and synthesis of manufacturing systems. Standard analytic models, as used extensively in the past, are ineffective for describing the general manufacturing situation due to their inability to deal with discontinuous and nonlinear phenomena. These limitations are transcended by algebraic models based on set structures. Set-theoretic and algebraic structures may be used to (1) express with precision a variety of important qualitative concepts such as hierarchies, (2) provide a uniform framework for more specialized theories such as automata theory and control theory, and (3) provide the groundwork for quantitative theories. By building on the results of other fields such as automata theory and computability theory, algebraic structures may be used as a general mathematical tool for studying the nature and limits of manufacturing systems. This paper shows how manufacturing systems may be modeled as automatons, and demonstrates the utility of this approach by discussing a number of theorems concerning the nature of manufacturing systems. In addition symbolic logic is used to formalize the Design Axioms, a set of generalized decision rules for design. The application of symbolic logic allows for the precise formulation of the Axioms and facilitates their interpretation in a logical programming language such as Prolog. Consequently, it is now possible to develop a consultive expert system for axiomatic design.

APA, Harvard, Vancouver, ISO, and other styles

17

Ebas, Nur Ain, Nor Shamsidah Amir Hamzah, Kavikumar Jacob, and Mohd Saifullah Rusiman. "Fuzzy Finite Switchboard Automata with Complete Residuated Lattices." International Journal of Engineering & Technology 7, no. 4.30 (November 30, 2018): 160. http://dx.doi.org/10.14419/ijet.v7i4.30.22099.

Full text

Abstract:

The theory of fuzzy finite switchboard automata (FFSA) is introduced by the use of general algebraic structures such as complete residuated lattices in order to enhance the process ability of FFSA. We established the notion of homomorphism, strong homomorphism and reverse homomorphism and shows some of its properties. The subsystem of FFSA is studied and the set of switchboard subsystem-forms a complete -sublattices is shown. The algorithm of FFSA with complete residuated lattices is given and an example is provided.

APA, Harvard, Vancouver, ISO, and other styles

18

Cardona, R., and N. Galatos. "The finite embeddability property for noncommutative knotted extensions of RL." International Journal of Algebra and Computation 25, no. 03 (April 9, 2015): 349–79. http://dx.doi.org/10.1142/s0218196715500010.

Full text

Abstract:

The finite embeddability property (FEP) for knotted extensions of residuated lattices holds under the assumption of commutativity, but fails in the general case. We identify weaker forms of the commutativity identity which ensure that the FEP holds. The results have applications outside of order algebra to non-classical logic, establishing the strong finite model property (SFMP) and the decidability for deductions, as well as to mathematical linguistics and automata theory, providing new conditions for recognizability of languages. Our proofs make use of residuated frames, developed in the context of algebraic proof theory.

APA, Harvard, Vancouver, ISO, and other styles

19

Letychevskyi, Oleksandr. "Algebraic School of V.M. Glushkov and Insertion Modeling." Cybernetics and Computer Technologies, no. 4 (December 4, 2023): 8–15. http://dx.doi.org/10.34229/2707-451x.23.4.2.

Full text

Abstract:

The Algebraic School of Viktor Mykhailovych Glushkov already has several generations of scientists, most of whom have already identified and are developing their own scientific directions. This school, started at the Institute of Cybernetics, was shaped by research that had the significance of inventions at the level of world science and the computer industry and in many ways predicted their further development. The work considers the formation of the paradigm of insertion modeling as a generalization of the main achievements of the Glushkov school, starting from the theory of automata and up to modern computer algebra systems. The main concepts from which insertion modeling was formed are considered, namely, symbolic computations, which were implemented even in the first personal machine of the MIR series. It is also the theory of agents and environments, parallel computing, and methods of artificial intelligence, developed at the Institute of Cybernetics, in the 60s and 70s. Numerous deployments of insertion modeling methods in cyber security, research in natural sciences, blockchain technology, in verification and testing of software and hardware, have shown the practicality and value of theoretical research conducted by followers of the Glushkov school. Keywords: symbolic computation, algebraic modeling, insertional modeling.

APA, Harvard, Vancouver, ISO, and other styles

20

Comin, Carlo. "Algebraic Characterization of the Class of Languages Recognized by Measure Only Quantum Automata." Fundamenta Informaticae 134, no. 3-4 (2014): 335–53. http://dx.doi.org/10.3233/fi-2014-1105.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Semerenko, Vasyl, and Oleksandr Voinalovich. "The simplification of computationals in error correction coding." Technology audit and production reserves 3, no. 2(59) (June 30, 2021): 24–28. http://dx.doi.org/10.15587/2706-5448.2021.233656.

Full text

Abstract:

The object of research is the processes of error correction transformation of information in automated systems. The research is aimed at reducing the complexity of decoding cyclic codes by combining modern mathematical models and practical tools. The main prerequisite for the complication of computations in deterministic linear error-correcting codes is the use of the algebraic representation as the main mathematical apparatus for these types of codes. Despite the universalism of the algebraic approach, its main drawback is the impossibility of taking into account the characteristic features of all subclasses of linear codes. In particular, the cyclic property is not taken into account at all for cyclic codes. Taking this property into account, one can go to a fundamentally different mathematical representation of cyclic codes – the theory of linear automata in Galois fields (linear finite-state machine). For the automaton representation of cyclic codes, it is proved that the problem of syndromic decoding of these codes in the general case is an NP-complete problem. However, if to use the proposed hierarchical approach to problems of complexity, then on its basis it is possible to carry out a more accurate analysis of the growth of computational complexity. Correction of single errors during one time interval (one iteration) of decoding has a linear decoding complexity on the length of the codeword, and error correction during m iterations of permutations of codeword bits has a polynomial complexity. According to three subclasses of cyclic codes, depending on the complexity of their decoding: easy decoding (linear complexity), iteratively decoded (polynomial complexity), complicate decoding (exponential complexity). Practical ways to reduce the complexity of computations are considered: alternate use of probabilistic and deterministic linear codes, simplification of software and hardware implementation by increasing the decoding time, use of interleaving. A method of interleaving is proposed, which makes it possible to simultaneously generate the burst errors and replace them with single errors. The mathematical apparatus of linear automata allows solving together the indicated problems of error correction coding.

APA, Harvard, Vancouver, ISO, and other styles

22

Jin, Jianhua, Qingguo Li, and Chunquan Li. "On Intuitionistic Fuzzy Context-Free Languages." Journal of Applied Mathematics 2013 (2013): 1–16. http://dx.doi.org/10.1155/2013/825249.

Full text

Abstract:

Taking intuitionistic fuzzy sets as the structures of truth values, we propose the notions of intuitionistic fuzzy context-free grammars (IFCFGs, for short) and pushdown automata with final states (IFPDAs). Then we investigate algebraic characterization of intuitionistic fuzzy recognizable languages including decomposition form and representation theorem. By introducing the generalized subset construction method, we show that IFPDAs are equivalent to their simple form, called intuitionistic fuzzy simple pushdown automata (IF-SPDAs), and then prove that intuitionistic fuzzy recognizable step functions are the same as those accepted by IFPDAs. It follows that intuitionistic fuzzy pushdown automata with empty stack and IFPDAs are equivalent by classical automata theory. Additionally, we introduce the concepts of Chomsky normal form grammar (IFCNF) and Greibach normal form grammar (IFGNF) based on intuitionistic fuzzy sets. The results of our study indicate that intuitionistic fuzzy context-free languages generated by IFCFGs are equivalent to those generated by IFGNFs and IFCNFs, respectively, and they are also equivalent to intuitionistic fuzzy recognizable step functions. Then some operations on the family of intuitionistic fuzzy context-free languages are discussed. Finally, pumping lemma for intuitionistic fuzzy context-free languages is investigated.

APA, Harvard, Vancouver, ISO, and other styles

23

Chen, Yu-Fang, Kai-Min Chung, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai, and Di-De Yen. "An Automata-Based Framework for Verification and Bug Hunting in Quantum Circuits." Proceedings of the ACM on Programming Languages 7, PLDI (June 6, 2023): 1218–43. http://dx.doi.org/10.1145/3591270.

Full text

Abstract:

We introduce a new paradigm for analysing and finding bugs in quantum circuits. In our approach, the problem is given by a ‍triple { P } C { Q } and the question is whether, given a set P of quantum states on the input of a circuit C , the set of quantum states on the output is equal to (or included in) a set Q . While this is not suitable to specify, e.g., functional correctness of a quantum circuit, it is sufficient to detect many bugs in quantum circuits. We propose a technique based on tree automata to compactly represent sets of quantum states and develop transformers to implement the semantics of quantum gates over this representation. Our technique computes with an algebraic representation of quantum states, avoiding the inaccuracy of working with floating-point numbers. We implemented the proposed approach in a prototype tool and evaluated its performance against various benchmarks from the literature. The evaluation shows that our approach is quite scalable, e.g., we managed to verify a large circuit with 40 qubits and 141,527 gates, or catch bugs injected into a circuit with 320 qubits and 1,758 gates, where all tools we compared with failed. In addition, our work establishes a connection between quantum program verification and automata, opening new possibilities to exploit the richness of automata theory and automata-based verification in the world of quantum computing.

APA, Harvard, Vancouver, ISO, and other styles

24

Attou, Samira, Ludovic Mignot, Clément Miklarz, and Florent Nicart. "Monadic Expressions and Their Derivatives." RAIRO - Theoretical Informatics and Applications 58 (2024): 6. http://dx.doi.org/10.1051/ita/2023014.

Full text

Abstract:

There are several well-known ways to compute derivatives of regular expressions due to Brzozowski, Antimirov or Lombardy and Sakarovitch. We propose another one which abstracts the underlying data structures (e.g. sets or linear combinations) using the notion of monad. As an example of this generalization advantage, we first introduce a new derivation technique based on the graded module monad and then show an application of this technique to generalize the parsing of expressions with capture groups and back references. We also extend operators defining expressions to any n-ary functions over value sets, such as classical operations (like negation or intersection for Boolean weights) or more exotic ones (like algebraic mean for rational weights). Moreover, we present how to compute a (non-necessarily finite) automaton from such an extended expression, using the Colcombet and Petrisan categorical definition of automata. These category theory concepts allow us to perform this construction in a unified way, whatever the underlying monad. Finally, to illustrate our work, we present a Haskell implementation of these notions using advanced techniques of functional programming, and we provide a web interface to manipulate concrete examples.

APA, Harvard, Vancouver, ISO, and other styles

25

Gulistan, Muhammad, Feng Feng, Madad Khan, and Aslıhan Sezgin. "Characterizations of Right Weakly Regular Semigroups in Terms of Generalized Cubic Soft Sets." Mathematics 6, no. 12 (November 30, 2018): 293. http://dx.doi.org/10.3390/math6120293.

Full text

Abstract:

Cubic sets are the very useful generalization of fuzzy sets where one is allowed to extend the output through a subinterval of [ 0 , 1 ] and a number from [ 0 , 1 ] . Generalized cubic sets generalized the cubic sets with the help of cubic point. On the other hand Soft sets were proved to be very effective tool for handling imprecision. Semigroups are the associative structures have many applications in the theory of Automata. In this paper we blend the idea of cubic sets, generalized cubic sets and semigroups with the soft sets in order to develop a generalized approach namely generalized cubic soft sets in semigroups. As the ideal theory play a fundamental role in algebraic structures through this we can make a quotient structures. So we apply the idea of neutrosophic cubic soft sets in a very particular class of semigroups namely weakly regular semigroups and characterize it through different types of ideals. By using generalized cubic soft sets we define different types of generalized cubic soft ideals in semigroups through three different ways. We discuss a relationship between the generalized cubic soft ideals and characteristic functions and cubic level sets after providing some basic operations. We discuss two different lattice structures in semigroups and show that in the case when a semigroup is regular both structures coincides with each other. We characterize right weakly regular semigroups using different types of generalized cubic soft ideals. In this characterization we use some classical results as without them we cannot prove the inter relationship between a weakly regular semigroups and generalized cubic soft ideals. This generalization leads us to a new research direction in algebraic structures and in decision making theory.

APA, Harvard, Vancouver, ISO, and other styles

26

Bystrova, I. V., and B. P. Podkopaev. "Fault Isolation in Network of State Automates." Journal of the Russian Universities. Radioelectronics 23, no. 1 (February 28, 2020): 18–29. http://dx.doi.org/10.32603/1993-8985-2020-23-1-18-29.

Full text

Abstract:

Introduction. In the paper a fault isolation problem in the devices combining digital unit by functional diagnostics methods is considered. Networks of state automates are accepted as mathematical models of the devices. Assumed, that functional diagnostics devices for each network component are preliminarily constructed in an optimal way and they consist of a control automata and of a fault discriminator of unit dimension.Aim. To develop functional diagnostics method based on theoretical analysis allowing to decide fault isolation problem in networks of state automation and to reduce computational complexity and hardware redundancy.Materials and methods. An analysis of mathematical description of a network of state automation and functional diagnostics devices for each network component was presented in terms of algebraic theory of functional diagnosis of dynamic systems. A possibility to transform the set of known functional diagnostics devices of the network was demonstrated. The possibility provided a localization of the network component with an error, if the component was unique.Results. A searching procedure of the analytical equations determining supervision automata and fault discriminator for the whole network was proposed. The case when initial functional diagnostics devices for each network component were defined by scalar functions was considered. The obtained result was generalized to the case, when mentioned devices were defined by vector functions. The application of the described method was demonstrated in the example of construction functional diagnostics devices for simplified fragment of the device for forming priorities of mutual aircraft navigation system.Conclusion. Estimation of results by an order criterion was obtained. It was established that with an increase in the number of network components, the reduction of intentioned redundancy by functional diagnostics devices compared with the original version increased significantly.

APA, Harvard, Vancouver, ISO, and other styles

27

Denis, Laurent. "Méthodes fonctionnelles pour la transcendance en caractéristique finie." Bulletin of the Australian Mathematical Society 50, no. 2 (October 1994): 273–86. http://dx.doi.org/10.1017/s0004972700013733.

Full text

Abstract:

There are essentially two ways to obtain transcendence results in finite characteristic. The first, historically, is to use Ore's lemma and to prove that a series whose coefficients satisfy well-behaved divisibility properties cannot be a zero of an additive polynomial. This method is of the same kind as the method of p–automata. The second one is to try to imitate the usual methods in characteristic zero and to do transcendence theory with t–modules analogously to what we can do with algebraic groups. We want to show here that transcendence results over Fq(T) can also be obtained with the help of the variable T. If ec(z) is the Carlitz exponential function and e = ec(1), we obtain, in particular, that 1, e, …, e(p–2) (the P–2 first derivative of e with respect to T) are linearly independent over the algebraic closure of Fq(T). A corollary is that for every non-zero element α in Fq((1/T)), αpe and αec(e1/p) are transcendental over Fq(T). By changing the variable and using older results we also obtain the transcendence of ec(ω) for all ω ∈ Fq((1/T)) such that ω(T) and ω(Ti) are not zero and linearly dependent over Fq (Ti) (q > 2i + 1). Such u appear to be transcendental by the method of Mahler if i is not a power of p.

APA, Harvard, Vancouver, ISO, and other styles

28

Jones, Nick G., and Noah Linden. "Integrable spin chains and the Clifford group." Journal of Mathematical Physics 63, no. 10 (October 1, 2022): 101901. http://dx.doi.org/10.1063/5.0095870.

Full text

Abstract:

We construct new families of spin chain Hamiltonians that are local, integrable, and translationally invariant. To do so, we make use of the Clifford group that arises in quantum information theory. We consider translation invariant Clifford group transformations that can be described by matrix product operators (MPOs). We classify translation invariant Clifford group transformations that consist of a shift operator and an MPO of bond dimension two—this includes transformations that preserve locality of all Hamiltonians and those that lead to non-local images of particular operators but, nevertheless, preserve locality of certain Hamiltonians. We characterize translation invariant Clifford group transformations that take single-site Pauli operators to local operators on at most five sites—examples of Quantum Cellular Automata—leading to a discrete family of Hamiltonians that are equivalent to the canonical XXZ model under such transformations. For spin chains solvable by the algebraic Bethe ansatz, we explain how conjugating by an MPO affects the underlying integrable structure. This allows us to relate our results to the usual classifications of integrable Hamiltonians. We also treat the case of spin chains solvable by free fermions.

APA, Harvard, Vancouver, ISO, and other styles

29

KÁDÁR, ZOLTÁN, ANNALISA MARZUOLI, and MARIO RASETTI. "BRAIDING AND ENTANGLEMENT IN SPIN NETWORKS: A COMBINATORIAL APPROACH TO TOPOLOGICAL PHASES." International Journal of Quantum Information 07, supp01 (January 2009): 195–203. http://dx.doi.org/10.1142/s0219749909004785.

Full text

Abstract:

The spin network quantum simulator relies on the su(2) representation ring (or its q-deformed counterpart at q = root of unity) and its basic features naturally include (multipartite) entanglement and braiding. In particular, q-deformed spin network automata are able to perform efficiently approximate calculations of topological invarians of knots and 3-manifolds. The same algebraic background is shared by 2D lattice models supporting topological phases of matter that have recently gained much interest in condensed matter physics. These developments are motivated by the possibility to store quantum information fault-tolerantly in a physical system supporting fractional statistics since a part of the associated Hilbert space is insensitive to local perturbations. Most of currently addressed approaches are framed within a "double" quantum Chern–Simons field theory, whose quantum amplitudes represent evolution histories of local lattice degrees of freedom.We propose here a novel combinatorial approach based on "state sum" models of the Turaev–Viro type associated with SU(2)q-colored triangulations of the ambient 3-manifolds. We argue that boundary 2D lattice models (as well as observables in the form of colored graphs satisfying braiding relations) could be consistently addressed. This is supported by the proof that the Hamiltonian of the Levin–Wen condensed string net model in a surface Σ coincides with the corresponding Turaev–Viro amplitude on Σ × [0,1] presented in the last section.

APA, Harvard, Vancouver, ISO, and other styles

30

Picantin, Matthieu. "Automatic Structures for Torus Link Groups." Journal of Knot Theory and Its Ramifications 12, no. 06 (September 2003): 833–66. http://dx.doi.org/10.1142/s0218216503002627.

Full text

Abstract:

A general result of Epstein and Thurston implies that all link groups are automatic, but the proof provides no explicit automaton. Here we show that the groups of all torus links are groups of fractions of so-called Garside monoids, i.e., roughly speaking, monoids with a good theory of divisibility, which allows us to reprove that those groups are automatic, but, in addition, gives a completely explicit description of the involved automata, thus partially answering a question of D. F. Holt.

APA, Harvard, Vancouver, ISO, and other styles

31

Gornev, E. S., and I. V. Matyushkin. "A discussion of S.M. Krylov’s book «Neocybernetics» (2008)." Russian Technological Journal 9, no. 6 (December 2, 2021): 73–87. http://dx.doi.org/10.32362/2500-316x-2021-9-6-73-87.

Full text

Abstract:

A comparative analysis of the “general formal technology (GFT)” by S. M. Krylov is carried out in the context of the published book of the authors “General Theory of Technologies and Microelectronics” (2020) and on the basis of his work of 2008. Despite the abstractness of the algebraic-algorithmic approach, Krylov offers a number of specific constructions that are in demand during the fourth industrial revolution and for the future development of industrial technology in nanoelectronics and biotechnology. Industrial technology is considered as a complex object of management, i.e., it is the object of study of the new discipline «neocybernetics». Although the foundations of this approach were laid in 1930s–1960s within the framework of logical and mathematical research, its expansion is inevitable when using self-organization processes to obtain functional supramolecular structures in technological processes of nanoelectronics (for example, DNA origami engineering). The issues of complexity quantification for a product itself (structure) and its manufacturing technology, or, according to Krylov, the complexity of technological automata, have become even more relevant than before. The theoretical issues of self-organization, the development of artificial life, and the creation of self-replicating technical systems also seem promising for solution. In our opinion, Krylov’s formal technology is an important “block” in the advancement of general theory of technologies (GTT) useful for describing the technology at the levels: operation, route, and process. We would like to encourage a wide range of readers to study the book and form a steady interest in general technological issues. The value of GTT and GFT extends beyond the sphere of technology and, in a narrow sense, factory production, but also into the area of «fine» regulation of physiology in biological objects and pharmacy, as well as into the problem field of cognitive sciences, psychology, and education. when the focus is on the personality structure and heterogeneous constructs «floating in the sea of the unconscious». Both S.M. Krylov and we demonstrate that the issues of industrial technology cannot be considered without abstract formalization and without reference to philosophy.

APA, Harvard, Vancouver, ISO, and other styles

32

Гайдур, Галина Іванівна, Сергій Олександрович Гахов, and Віталій Вікторович Марченко. "Метод побудови динамічної моделі логічного об’єкта інформаційної системи та визначення закону його функціонування." RADIOELECTRONIC AND COMPUTER SYSTEMS, no. 1 (February 23, 2022): 129–40. http://dx.doi.org/10.32620/reks.2022.1.10.

Full text

Abstract:

The subject of the research in this article is the methods for detecting intrusions into the information systems of organizations to justify the requirements for the functioning of the monitoring agent of the selected logical object. The aim is to develop a method for building a dynamic model of the logical object of the information system and determine the law of its operation. Tasks: to substantiate the need to create security monitoring agents for logical objects of information systems; identify the main functions of security monitoring agents for logical objects; to propose a method for building a dynamic model of the functioning of a logical object and determining the law of its functioning. The methods used are abstraction, system approach, and methods of mathematical modeling using the provisions of the theory of finite automata. The following results were obtained. A method for constructing a dynamic model of a logical object of an information system is proposed. The dynamic model of the operation of the selected logical object reflects the allowable processes in the space of states that occur during the implementation of functions following the specifications defined by the protocol. This dynamic model is represented by a system of algebraic equations in the space of states, which are formed because of the formalization of the processes of realization of certain functions. The solution of a system of algebraic equations in the space of states as a dynamic model of a logical object is a regular expression for a set of admissible processes. This regular expression defines the set of possible trajectories in the space of states, which is the law of operation of this logical object. Conclusions. The proposed method for building a dynamic model of the logical object in contrast to the existing one is based on the formalization of the processes of implementing of partial functions of the protocol, which allows determining the law of the selected logical object, to ensure the adequacy and accuracy of the model. The law of functioning is the basis for the substantiation of initial data for a statement of problems of identification and diagnosing of a condition of the safety of logical objects of an information system. The solution to these problems is needed to substantiate the requirements for the functioning of the agent to monitor the state of the selected logical object and respond to its changes.vulnerabilities of information systems; the logical object of the information system; information system security status; dynamic model of a logical object; the law of functioning of a logical object

APA, Harvard, Vancouver, ISO, and other styles

33

Brieussel, Jérémie. "An automata group of intermediate growth and exponential activity." Journal of Group Theory 21, no. 4 (July 1, 2018): 573–78. http://dx.doi.org/10.1515/jgth-2017-0046.

Full text

Abstract:

AbstractWe give a new example of an automata group of intermediate growth. It is generated by an automaton with four states on an alphabet with eight letters. This automata group has exponential activity and its limit space is not simply connected.

APA, Harvard, Vancouver, ISO, and other styles

34

Wiweger, Antoni. "Free Games over Coloured Automata." Fundamenta Informaticae 8, no. 2 (April 1, 1985): 199–224. http://dx.doi.org/10.3233/fi-1985-8204.

Full text

Abstract:

Concepts of category theory are applied to the investigation of some relations between automata and abstract games. The notion of a coloured automaton introduced in this paper provides a framework for a unified treatment of automata and abstract games. Both games and automata can be viewed as special cases of this general notion. A coloured automaton is defined to be a Mealy automaton with the additional structure of a coloured graph on the set of inputs. Various categories of coloured automata, automata, and games are described. It is shown that some forgetful functors between these categories have left adjoints, and explicit constructions of these adjoints are given. The main result is Theorem 5.5 which describes a construction of a free abstract game over a coloured automaton satisfying some additional conditions.

APA, Harvard, Vancouver, ISO, and other styles

35

Champarnaud, J. M., and G. Hansel. "AUTOMATE, a computing package for automata and finite semigroups." Journal of Symbolic Computation 12, no. 2 (August 1991): 197–220. http://dx.doi.org/10.1016/s0747-7171(08)80125-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

D'Angeli, Daniele, Dominik Francoeur, Emanuele Rodaro, and Jan Philipp Wächter. "On the orbits of automaton semigroups and groups." Algebra and Discrete Mathematics 33, no. 1 (2022): 1–29. http://dx.doi.org/10.12958/adm1692.

Full text

Abstract:

We investigate the orbits of automaton semigroups and groups to obtain algorithmic and structural results, both for general automata but also for some special subclasses. First, we show that a more general version of the finiteness problem for automaton groups is undecidable. This problem is equivalent to the finiteness problem for left principal ideals in automaton semigroups generated by complete and reversible automata. Then, we look at w-word (i.\,e.\ right infinite words) with a finite orbit. We show that every automaton yielding an w-word with a finite orbit already yields an ultimately periodic one, which is not periodic in general, however. On the algorithmic side, we observe that it is not possible to decide whether a given periodic w-word has an infinite orbit and that we cannot check whether a given reversible and complete automaton admits an w-word with a finite orbit, a reciprocal problem to the finiteness problem for automaton semigroups in the reversible case. Finally, we look at automaton groups generated by reversible but not bi-reversible automata and show that many words have infinite orbits under the action of such automata.

APA, Harvard, Vancouver, ISO, and other styles

37

FABERT, OLIVER. "LOCAL SYMPLECTIC FIELD THEORY." International Journal of Mathematics 24, no. 05 (May 2013): 1350041. http://dx.doi.org/10.1142/s0129167x13500419.

Full text

Abstract:

Generalizing local Gromov–Witten theory, in this paper we define a local version of symplectic field theory. When the symplectic manifold with cylindrical ends is four-dimensional and the underlying simple curve is regular by automatic transversality, we establish a transversality result for all its multiple covers and discuss the resulting algebraic structures.

APA, Harvard, Vancouver, ISO, and other styles

38

Peltier, Nicolas. "Tree Automata and Automated Model Building." Fundamenta Informaticae 30, no. 1 (1997): 59–81. http://dx.doi.org/10.3233/fi-1997-30105.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Martiník, Ivo. "Automation of Presentation Record Production Based on Rich-Media Technology Using SNT Petri Nets Theory." Scientific World Journal 2015 (2015): 1–19. http://dx.doi.org/10.1155/2015/303705.

Full text

Abstract:

Rich-media describes a broad range of digital interactive media that is increasingly used in the Internet and also in the support of education. Last year, a special pilot audiovisual lecture room was built as a part of the MERLINGO (MEdia-rich Repository of LearnING Objects) project solution. It contains all the elements of the modern lecture room determined for the implementation of presentation recordings based on the rich-media technologies and their publication online or on-demand featuring the access of all its elements in the automated mode including automatic editing. Property-preserving Petri net process algebras (PPPA) were designed for the specification and verification of the Petri net processes. PPPA does not need to verify the composition of the Petri net processes because all their algebraic operators preserve the specified set of the properties. These original PPPA are significantly generalized for the newly introduced class of the SNT Petri process and agent nets in this paper. The PLACE-SUBST and ASYNC-PROC algebraic operators are defined for this class of Petri nets and their chosen properties are proved. The SNT Petri process and agent nets theory were significantly applied at the design, verification, and implementation of the programming system ensuring the pilot audiovisual lecture room functionality.

APA, Harvard, Vancouver, ISO, and other styles

40

Dunets, Andriy, Gerhard Schellhorn, and Wolfgang Reif. "Automated Flaw Detection in Algebraic Specifications." Journal of Automated Reasoning 45, no. 4 (January 29, 2010): 359–95. http://dx.doi.org/10.1007/s10817-010-9166-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Ganty, Pierre, Elena Gutiérrez, and Pedro Valero. "A Congruence-Based Perspective on Finite Tree Automata." Fundamenta Informaticae 184, no. 1 (January 10, 2022): 1–47. http://dx.doi.org/10.3233/fi-2021-2091.

Full text

Abstract:

We provide new insights on the determinization and minimization of tree automata using congruences on trees. From this perspective, we study a Brzozowski’s style minimization algorithm for tree automata. First, we prove correct this method relying on the following fact: when the automata-based and the language-based congruences coincide, determinizing the automaton yields the minimal one. Such automata-based congruences, in the case of word automata, are defined using pre and post operators. Now we extend these operators to tree automata, a task that is particularly challenging due to the reduced expressive power of deterministic top-down (or equivalently co-deterministic bottom-up) automata. We leverage further our framework to offer an extension of the original result by Brzozowski for word automata.

APA, Harvard, Vancouver, ISO, and other styles

42

Otto, Friedrich. "A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*." Fundamenta Informaticae 180, no. 1-2 (May 12, 2021): 77–101. http://dx.doi.org/10.3233/fi-2021-2035.

Full text

Abstract:

A complete taxonomy is presented for restarting automata without auxiliary symbols. In this taxonomy, the language classes that are accepted by deterministic and nondeterministic, monotone, weakly monotone, and non-monotone, shrinking and length-reducing restarting automata are compared to each other with respect to inclusion. As it turns out, the 45 types of restarting automata considered yield 29 different classes of languages. By presenting a collection of rather simple example languages, it is shown that, for any two of these language classes ℒ1 and ℒ2, the class ℒ1 is a subclass of ℒ2 if and only if ℒ1 is defined by a type of restarting automaton that is a restriction of a type of restarting automaton that defines the class ℒ2.

APA, Harvard, Vancouver, ISO, and other styles

43

Kutylowski, Miroslaw. "Chains of Finite Automat a with Bounded Number of Chains1." Fundamenta Informaticae 11, no. 3 (July 1, 1988): 267–73. http://dx.doi.org/10.3233/fi-1988-11304.

Full text

Abstract:

Chains of finite automata are considered. We show that if the lowest automaton in a chain controls movements of the common reading head then computing power of the chain is very limited. This is a generalization of Krohn-Rhodes theorem on one-way automata.

APA, Harvard, Vancouver, ISO, and other styles

44

Löding, Christof, and Max Philip Stachon. "On Minimization and Learning of Deterministic ω-Automata in the Presence of Don’t Care Words." Fundamenta Informaticae 189, no. 1 (July 7, 2023): 69–91. http://dx.doi.org/10.3233/fi-222152.

Full text

Abstract:

We study minimization problems for deterministic ω-automata in the presence of don’t care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don’t care words. We derive that from a more general result from which one also obtains an efficient minimization algorithm for deterministic parity automata with informative right-congruence (without don’t care words). We then analyze languages of don’t care words with a trivial right-congruence. For such sets of don’t care words it is known that weak deterministic Büchi automata (WDBA) have a unique minimal automaton that can be efficiently computed from a given WDBA (Eisinger, Klaedtke 2006). We give a congruence-based characterization of the corresponding minimal WDBA, and show that the don’t care minimization results for WDBA do not extend to deterministic ω-automata with informative right-congruence: for this class there is no unique minimal automaton for a given don’t care set with trivial right congruence, and the minimization problem is NP-hard. Finally, we extend an active learning algorithm for WDBA (Maler, Pnueli 1995) to the setting with an additional set of don’t care words with trivial right-congruence.

APA, Harvard, Vancouver, ISO, and other styles

45

Fernau, Henning, Martin Kutrib, and Matthias Wendlandt. "Self-Verifying Pushdown and Queue Automata." Fundamenta Informaticae 180, no. 1-2 (May 12, 2021): 1–28. http://dx.doi.org/10.3233/fi-2021-2032.

Full text

Abstract:

We study the computational and descriptional complexity of self-verifying pushdown automata (SVPDA) and self-verifying realtime queue automata (SVRQA). A self-verifying automaton is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. We show that SVPDA and SVRQA are automata characterizations of so-called complementation kernels, that is, context-free or realtime nondeterministic queue automaton languages whose complement is also context free or accepted by a realtime nondeterministic queue automaton. So, the families of languages accepted by SVPDA and SVRQA are strictly between the families of deterministic and nondeterministic languages. Closure properties and various decidability problems are considered. For example, it is shown that it is not semidecidable whether a given SVPDA or SVRQA can be made self-verifying. Moreover, we study descriptional complexity aspects of these machines. It turns out that the size trade-offs between nondeterministic and self-verifying as well as between self-verifying and deterministic automata are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the former system to the latter.

APA, Harvard, Vancouver, ISO, and other styles

46

Pighizzini, Giovanni, and Luca Prigioniero. "Non-Self-Embedding Grammars and Descriptional Complexity." Fundamenta Informaticae 180, no. 1-2 (May 12, 2021): 103–22. http://dx.doi.org/10.3233/fi-2021-2036.

Full text

Abstract:

Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the number of states of nondeterministic and deterministic automata equivalent to given non-self-embedding grammars. In particular, each non-self-embedding grammar of size s can be converted into an equivalent nondeterministic automaton which has an exponential size in s and into an equivalent deterministic automaton which has a double exponential size in s. These costs are shown to be optimal. Moreover, they do not change if the larger class of quasi-non-self-embedding grammars, which still generate only regular languages, is considered. In the case of letter bounded languages, the cost of the conversion of non-self-embedding grammars and quasi-non-self-embedding grammars into deterministic automata reduces to an exponential of a polynomial in s.

APA, Harvard, Vancouver, ISO, and other styles

47

Černý, Anton, and Jozef Gruska. "Modular Real-Time Trellis Automata." Fundamenta Informaticae 9, no. 3 (July 1, 1986): 253–82. http://dx.doi.org/10.3233/fi-1986-9302.

Full text

Abstract:

A new type of nonhomogeneous real time trellis automata, the so-called modular trellis automata, is introduced and various results concerning their normal forms, power, simulations, and decision problems are shown. Modular trellis automata are a mathematical abstraction, in the form of a recognizer, of an intuitive notion of an array of simple processors assembled in a simple and modular way. Distribution of processors in a real-time trellis automaton forms a two-dimensional structure called trellis. Basic characterizations and properties of modular trellises are summarized and modularity of various special trellises – regular, product, self-embedding, and self-overlapping – is investigated.

APA, Harvard, Vancouver, ISO, and other styles

48

Beyne, Tim, and Michiel Verbauwhede. "Integral Cryptanalysis Using Algebraic Transition Matrices." IACR Transactions on Symmetric Cryptology 2023, no. 4 (December 8, 2023): 244–69. http://dx.doi.org/10.46586/tosc.v2023.i4.244-269.

Full text

Abstract:

In this work we introduce algebraic transition matrices as the basis for a new approach to integral cryptanalysis that unifies monomial trails (Hu et al., Asiacrypt 2020) and parity sets (Boura and Canteaut, Crypto 2016). Algebraic transition matrices allow for the computation of the algebraic normal form of a primitive based on the algebraic normal forms of its components by means of wellunderstood operations from linear algebra. The theory of algebraic transition matrices leads to better insight into the relation between integral properties of F and F−1. In addition, we show that the link between invariants and eigenvectors of correlation matrices (Beyne, Asiacrypt 2018) carries over to algebraic transition matrices. Finally, algebraic transition matrices suggest a generalized definition of integral properties that subsumes previous notions such as extended division properties (Lambin, Derbez and Fouque, DCC 2020). On the practical side, a new algorithm is described to search for these generalized properties and applied to Present, resulting in new properties. The algorithm can be instantiated with any existing automated search method for integral cryptanalysis.

APA, Harvard, Vancouver, ISO, and other styles

49

Dobronravov, Egor, Nikita Dobronravov, and Alexander Okhotin. "On the Length of Shortest Strings Accepted by Two-way Finite Automata." Fundamenta Informaticae 180, no. 4 (June 30, 2021): 315–31. http://dx.doi.org/10.3233/fi-2021-2044.

Full text

Abstract:

Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than (2nn+1), with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e(1+o(1))mn(log n− log m).

APA, Harvard, Vancouver, ISO, and other styles

50

Sakai, Masahiko, Toshiki Sakabe, and Yasuyoshi Inagaki. "Algebraic specification and automatic generation of compilers." Systems and Computers in Japan 23, no. 2 (1992): 1–13. http://dx.doi.org/10.1002/scj.4690230201.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!