Relevant bibliographies by topics / Algebraic automata theory

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature 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 lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

Journal articles on the topic "Algebraic automata theory"

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
More sources

Dissertations / Theses on the topic "Algebraic automata theory"

1

Cazalis, Daniel S. "Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications." FIU Digital Commons, 2007. http://digitalcommons.fiu.edu/etd/8.

Full text
Abstract:
Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.
APA, Harvard, Vancouver, ISO, and other styles
2

Büchse, Matthias. "Algebraic decoder specification: coupling formal-language theory and statistical machine translation." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-159266.

Full text
Abstract:
The specification of a decoder, i.e., a program that translates sentences from one natural language into another, is an intricate process, driven by the application and lacking a canonical methodology. The practical nature of decoder development inhibits the transfer of knowledge between theory and application, which is unfortunate because many contemporary decoders are in fact related to formal-language theory. This thesis proposes an algebraic framework where a decoder is specified by an expression built from a fixed set of operations. As yet, this framework accommodates contemporary syntax-based decoders, it spans two levels of abstraction, and, primarily, it encourages mutual stimulation between the theory of weighted tree automata and the application.
APA, Harvard, Vancouver, ISO, and other styles
3

Dando, Louis-Marie. "Expressivité des automates pondérés circulaires et boustrophédons." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0130/document.

Full text
Abstract:
Cette thèse porte sur certaines extensions des automates pondérés, et étudie les séries qu’ils réalisent en fonction de la nature des poids.Ces extensions se distinguent par les mouvements supplémentaires autorisés à la tête de lecture de l’automate : retour au début du mot pour les automates circulaires, changement de sens de lecture pour les automates boustrophédons.Dans le cas général, les automates pondérés circulaires sont plus puissants que les automates unidirectionnels classiques, et moins puissants que les boustrophédons.On introduit de plus les expressions de Hadamard, qui sont une extension des expressions rationnelles et qui permettent de dénoter le comportement des automates circulaires. Les aspects algorithmiques de cette conversion sont étudiés dans le cas où les poids appartiennent à un semi-anneau rationnellement additif.On montre que lorsque les poids sont des nombres rationnels, réels ou complexes, les automates circulaires sont aussi expressifs que les boustrophédons.Enfin, si les poids forment un bi-monoïde localement fini, les automates boustrophédons ne sont pas plus expressifs que les automates pondérés classsiques
This thesis deals with some extensions of weighted automata,and studies the series they can realisedepending on the nature of their weigths.These extensions are characterised by howthe input head of the automaton is allowed to move:rotating automata can go back at the beginning of the word,and two-way automata can change the reading direction.In the general setting, weigthed rotating automata are morepowerful than classical one-way automata, and less powerfulthan two-way ones.Moreover, we introduce Hadamard expressions,which are an extension of rational expressions and can denotethe behaviour of rotating automata.The algorithms for this conversion are studied when the weights belong toa rationally additive semiring.Then, rotating automata are shown as expressive as two-way automatain the case of rational, real or complex numbers.It is also proved that two-way and one-way automataare equivalent when weighted on a locally finite bimonoid
APA, Harvard, Vancouver, ISO, and other styles
4

Soyez-Martin, Claire. "From semigroup theory to vectorization : recognizing regular languages." Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB052.

Full text
Abstract:
L'évaluation efficace des expressions régulières constitue un défi persistant depuis de nombreuses décennies. Au fil du temps, des progrès substantiels ont été réalisés grâce à une variété d'approches, allant de nouveaux et ingénieux algorithmes à des optimisations complexes de bas niveau.Les outils de pointe de ce domaine utilisent ces techniques d'optimisation, et repoussent constamment les limites de leur efficacité. Une avancée notoire réside dans l'intégration de la vectorisation, qui exploite une forme de parallélisme de bas niveau pour traiter l'entrée par blocs, entraînant ainsi d'importantes améliorations de performances. Malgré une recherche approfondie sur la conception d'algorithmes sur mesure pour des tâches particulières, ces solutions manquent souvent de généralisabilité, car la méthodologie sous-jacente à ces algorithmes ne peut pas être appliquée de manière indiscriminée à n'importe quelle expression régulière, ce qui rend difficile son intégration dans les outils existants.Cette thèse présente un cadre théorique permettant de générer des programmes vectorisés particuliers capables d'évaluer les expressions régulières correspondant aux expressions rationnelles appartenant à une classe logique donnée. L'intérêt de ces programmes vectorisés vient de l'utilisation de la théorie algébrique des automates, qui offre certains outils algébriques permettant de traiter les lettres en parallèle. Ces outils permettent également d'analyser les langages réguliers plus finement, offrent accès à des optimisations des programmes vectorisés basées sur les propriétés algébriques de ces langages. Cette thèse apporte des contributions dans deux domaines. D'une part, nous présentons des implémentations et des benchmarks préliminaires, afin d'étudier les possibilités offertes par l'utilisation de l'algèbre et de la vectorisation dans les algorithmes d'évaluation des expressions régulières. D'autre part, nous proposons des algorithmes capables de générer des programmes vectorisés reconnaissant les langages appartenant à deux classes d'expressions rationnelles, la logique du premier ordre et sa restriction aux formules utilisant au plus deux variables
The pursuit of optimizing regular expression validation has been a long-standing challenge,spanning several decades. Over time, substantial progress has been made through a vast range of approaches, spanning from ingenious new algorithms to intricate low-level optimizations.Cutting-edge tools have harnessed these optimization techniques to continually push the boundaries of efficient execution. One notable advancement is the integration of vectorization, a method that leverage low-level parallelism to process data in batches, resulting in significant performance enhancements. While there has been extensive research on designing handmade tailored algorithms for particular languages, these solutions often lack generalizability, as the underlying methodology cannot be applied indiscriminately to any regular expression, which makes it difficult to integrate to existing tools.This thesis provides a theoretical framework in which it is possible to generate vectorized programs for regular expressions corresponding to rational expressions in a given class. To do so, we rely on the algebraic theory of automata, which provides tools to process letters in parallel. These tools also allow for a deeper understanding of the underlying regular language, which gives access to some properties that are useful when producing vectorized algorithms. The contribution of this thesis is twofold. First, it provides implementations and preliminary benchmarks to study the potential efficiency of algorithms using algebra and vectorization. Second, it gives algorithms that construct vectorized programs for languages in specific classes of rational expressions, namely the first order logic and its subset restricted to two variables
APA, Harvard, Vancouver, ISO, and other styles
5

Mahesar, Quratul-ain. "Computing relatively large algebraic structures by automated theory exploration." Thesis, University of Birmingham, 2014. http://etheses.bham.ac.uk//id/eprint/5023/.

Full text
Abstract:
Automated reasoning technology provides means for inference in a formal context via a multitude of disparate reasoning techniques. Combining different techniques not only increases the effectiveness of single systems but also provides a more powerful approach to solving hard problems. Consequently combined reasoning systems have been successfully employed to solve non-trivial mathematical problems in combinatorially rich domains that are intractable by traditional mathematical means. Nevertheless, the lack of domain specific knowledge often limits the effectiveness of these systems. In this thesis we investigate how the combination of diverse reasoning techniques can be employed to pre-compute additional knowledge to enable mathematical discovery in finite and potentially infinite domains that is otherwise not feasible. In particular, we demonstrate how we can exploit bespoke symbolic computations and automated theorem proving to automatically compute and evolve the structural knowledge of small size finite structures in the algebraic theory of quasigroups. This allows us to increase the solvability horizon of model generation systems to find solution models for large size finite algebraic structures previously unattainable. We also present an approach to exploring infinite models using a mixture of automated tools and user interaction to iteratively inspect the structure of solutions and refine search. A practical implementation combines a specialist term rewriting system with bespoke graph algorithms and visualization tools and has been applied to solve the generalized version of Kuratowski's classical closure-complement problem from point-set topology that had remained open for several years.
APA, Harvard, Vancouver, ISO, and other styles
6

Chilton, Christopher James. "An algebraic theory of componentised interaction." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:9908e7a0-4edd-4c08-9701-d010bcaaff6e.

Full text
Abstract:
This thesis provides a specification theory with strong algebraic and compositionality properties, allowing for the systematic construction of new components out of existing ones, while ensuring that given properties continue to hold at each stage of system development. The theory shares similarities with the interface automata of de Alfaro and Henzinger, but is linear-time in the style of Dill's trace theory, and is endowed with a richer collection of operators. Components are assumed to communicate with one another by synchronisation of input and output actions, with the component specifying the allowed sequences of interactions between itself and the environment. When the environment produces an interaction that the component is unwilling to receive, a communication mismatch occurs, which can correspond to run-time error or underspecification. These are modelled uniformly as inconsistencies. A linear-time refinement preorder corresponding to substitutivity preserves the absence of inconsistency under all environments, allowing for the safe replacement of components at run-time. To build complex systems, a range of compositional operators are introduced, including parallel composition, logical conjunction and disjunction, hiding, and quotient. These can be used to examine the structural behaviour of a system, combine independently developed requirements, abstract behaviour, and incrementally synthesise missing components, respectively. It is shown that parallel composition is monotonic under refinement, conjunction and disjunction correspond to the meet and join operations on the refinement preorder, and quotient is the adjoint of parallel composition. Full abstraction results are presented for the equivalence defined as mutual refinement, a consequence of the refinement being the weakest preorder capturing substitutivity. Extensions of the specification theory with progress-sensitivity (ensuring that refinement cannot introduce quiescence) and real-time constraints on when interactions may and may not occur are also presented. These theories are further complemented by assume-guarantee frameworks for supporting component-based reasoning, where contracts (characterising sets of components) separate the assumptions placed on the environment from the guarantees provided by the components. By defining the compositional operators directly on contracts, sound and complete assume-guarantee rules are formulated that preserve both safety and progress. Examples drawn from distributed systems are used to demonstrate how these rules can be used for mechanically deriving component-based designs.
APA, Harvard, Vancouver, ISO, and other styles
7

Ferte, Julien. "Régularité et contraintes de descendance : équations algébriques." Thesis, Aix-Marseille, 2014. http://www.theses.fr/2014AIXM4713.

Full text
Abstract:
Ce mémoire est constitué de 3 parties.La NP-complétude de la satisfaction de combinaisons booléennes de contraintes de sous-arbres est démontrée dans l'article [Ven87] ; la partie I de ce mémoire étudie dans quelle mesure l'ajout de contraintes régulières laisse espérer conserver la complexité NP. Ce modèle étendu définit une nouvelle classe de langages dont l'expressivité est comparée à celle des Rigid Tree Automata [JKV11]. Puis un début de formalisation des t-dags est donné.Les patterns ont été étudiés, principalement du point de vue des contraintes sur les données qu'ils demandent. La partie II de ce mémoire les étudie plus finement, en mettant de côté les données. Les squelettes sont définis en tant qu'intermédiaire de calcul et le fait que leur syntaxe caractérise leur sémantique est démontré. Puis un lemme de pompage est donné dans un cas restreint, un autre dans le cas général est étudié et conjecturé. Ensuite des fragments de combinaisons booléennes de patterns sont comparés en expressivité pour terminer avec l'étude de la complexité des problèmes de model-checking, satisfaisabilité et DTD-satisfaisabilité sur les dits fragments.Le contenu de la partie III constitue l'article [FMS11], c'est la démonstration de la caractérisation des langages des automates fortement déterministes de niveau 2 par des systèmes d'équations récurrentes caténatives. Celle-ci utilise, entre autres, des techniques de réécriture, la notion d'inconnues non-réécrivables et les ordres noethériens. Cette caractérisation constitue le cas de base de la récurrence démontrée dans [Sén07]
This thesis is in 3 parts.The NP-completeness of satisfiability of boolean combinations of subtree constraints is shown in the article [Ven87] ; in the part I of this thesis, we study whether adding regular contraints lets hope for keeping the same complexity. This extended model defines a new class of languages which is compared in expressivity to the Rigid Tree Automata [JKV11]. Then a begining of formalisation of the t-dags is developped.The patterns have been studied mainly from the point of view of the constraints they demand on the data. The part II of this thesis study them more finely, by putting aside the data. The skeletons are defined as calculus intermediate and the characterisation holding between their syntax and their semantics is shown. Then a pumping lemma is prooved in a restreict case, another one is conjectured in the most general case. Then fragments of boolean combinations of patterns are compared in expressivity, this parts ends with the study of complexity of model-checking, satisfiability and DTD-satisfiability on these fragments.The content of part III constitutes the article [FMS11], it is the demonstration of the characterisation of strongly-deterministic 2-level pushdown automata by recurrent catenative equation systems. This proof uses in particular, some rewriting techniques, unrewritable unknowns and noetherian orders. This characterisation provides the base case of the recurrence shown in [Sén07]
APA, Harvard, Vancouver, ISO, and other styles
8

Cordy, Brendan. "Coalgebraic automata and canonical models of Moore machines." Thesis, McGill University, 2008. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=111602.

Full text
Abstract:
We give a concise introduction to the coalgebraic theory of Moore machines, and building on [6], develop a method for constructing a final Moore machine based on a simple modal logic. Completeness for the logic follows easily from the finality construction, and we furthermore show how this logical framework can be used for machine learning.
APA, Harvard, Vancouver, ISO, and other styles
9

Katona, Gregory. "Field Theoretic Lagrangian From Off-Shell Supermultiplet Gauge Quotients." Doctoral diss., University of Central Florida, 2013. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/5958.

Full text
Abstract:
Recent efforts to classify off-shell representations of supersymmetry without a central charge have focused upon directed, supermultiplet graphs of hypercubic topology known as Adinkras. These encodings of Super Poincare algebras, depict every generator of a chosen supersymmetry as a node-pair transformtion between fermionic / bosonic component fields. This research thesis is a culmination of investigating novel diagrammatic sums of gauge quotients by supersymmetric images of other Adinkras, and the correlated building of field theoretic worldline Lagrangians to accommodate both classical and quantum venues. We find Ref [40], that such gauge quotients do not yield other stand alone or ”proper” Adinkras as afore sighted, nor can they be decomposed into supermultiplet sums, but are rather a connected ”Adinkraic network”. Their iteration, analogous to Weyl's construction for producing all finite-dimensional unitary representations in Lie algebras, sets off chains of algebraic paradigms in discrete-graph and continuous-field variables, the links of which feature distinct, supersymmetric Lagrangian templates. Collectively, these Adiankraic series air new symbolic genera for equation to phase moments in Feynman path integrals. Guided in this light, we proceed by constructing Lagrangians actions for the N = 3 supermultiplet YI /(iDI X) for I = 1, 2, 3, where YI and X are standard, Salam-Strathdee superfields: YI fermionic and X bosonic. The system, bilinear in the component fields exhibits a total of thirteen free parameters, seven of which specify Zeeman-like coupling to external background (magnetic) fluxes. All but special subsets of this parameter space describe aperiodic oscillatory responses, some of which are found to be surprisingly controlled by the golden ratio, ? ? 1.61803, Ref [52]. It is further determined that these Lagrangians allow an N = 3 ? 4 supersymmetric extension to the Chiral-Chiral and Chiral-twisted- Chiral multiplet, while a subset admits two inequivalent such extensions. In a natural progression, a continuum of observably and usefully inequivalent, finite-dimensional off-shell representations of worldline N = 4 extended supersymmetry are explored, that are variate from one another but in the value of a tuning parameter, Ref [53]. Their dynamics turns out to be nontrivial already when restricting to just bilinear Lagrangians. In particular, we find a 34-parameter family of bilinear Lagrangians that couple two differently tuned supermultiplets to each other and to external magnetic fluxes, where the explicit parameter dependence is unremovable by any field redefinition and is therefore observable. This offers the evaluation of X-phase sensitive, off-shell path integrals with promising correlations to group product decompositions and to deriving source emergences of higher-order background flux-forms on 2-dimensional manifolds, the stacks of which comprise space-time volumes. Application to nonlinear sigma models would naturally follow, having potential use in M- and F- string theories.
Ph.D.
Doctorate
Physics
Sciences
Physics
APA, Harvard, Vancouver, ISO, and other styles
10

Brunet, Paul. "Algebras of Relations : from algorithms to formal proofs." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSE1198/document.

Full text
Abstract:
Les algèbres de relations apparaissent naturellement dans de nombreux cadres, en informatique comme en mathématiques. Elles constituent en particulier un formalisme tout à fait adapté à la sémantique des programmes impératifs. Les algèbres de Kleene constituent un point de départ : ces algèbres jouissent de résultats de décidabilités très satisfaisants, et admettent une axiomatisation complète. L'objectif de cette thèse a été d'étendre les résultats connus sur les algèbres de Kleene à des extensions de celles-ci.Nous nous sommes tout d'abord intéressés à une extension connue : les algèbres de Kleene avec converse. La décidabilité de ces algèbres était déjà connue, mais l'algorithme prouvant ce résultat était trop compliqué pour être utilisé en pratique. Nous avons donné un algorithme plus simple, plus efficace, et dont la correction est plus facile à établir. Ceci nous a permis de placer ce problème dans la classe de complexité PSpace-complete.Nous avons ensuite étudié les allégories de Kleene. Sur cette extension, peu de résultats étaient connus. En suivant des résultats sur des algèbres proches, nous avons établi l'équivalence du problème d'égalité dans les allégories de Kleene à l'égalité de certains ensembles de graphes. Nous avons ensuite développé un modèle d'automate original (les automates de Petri), basé sur les réseaux de Petri, et avons établi l'équivalence de notre problème original avec le problème de comparaison de ces automates. Nous avons enfin développé un algorithme pour effectuer cette comparaison dans le cadre restreint des treillis de Kleene sans identité. Cet algorithme utilise un espace exponentiel. Néanmoins, nous avons pu établir que la comparaison d'automates de Petri dans ce cas est ExpSpace-complète. Enfin, nous nous sommes intéressés aux algèbres de Kleene Nominales. Nous avons réalisé que les descriptions existantes de ces algèbres n'étaient pas adaptées à la sémantique relationnelle des programmes. Nous les avons donc modifiées pour nos besoins, et ce faisant avons trouvé diverses variations naturelles de ce modèle. Nous avons donc étudié en détails et en Coq les ponts que l'on peut établir entre ces variantes, et entre le modèle “classique” et notre nouvelle version
Algebras of relations appear naturally in many contexts, in computer science as well as in mathematics. They constitute a framework well suited to the semantics of imperative programs. Kleene algebra are a starting point: these algebras enjoy very strong decidability properties, and a complete axiomatisation. The goal of this thesis was to export known results from Kleene algebra to some of its extensions. We first considered a known extension: Kleene algebras with converse. Decidability of these algebras was already known, but the algorithm witnessing this result was too complicated to be practical. We proposed a simpler algorithm, more efficient, and whose correctness is easier to establish. It allowed us to prove that this problem lies in the complexity class PSpace-complete.Then we studied Kleene allegories. Few results were known about this extension. Following results about closely related algebras, we established the equivalence between equality in Kleene allegories and equality of certain sets of graphs. We then developed an original automaton model (so-called Petri automata), based on Petri nets. We proved the equivalence between the original problem and comparing these automata. In the restricted setting of identity-free Kleene lattices, we also provided an algorithm performing this comparison. This algorithm uses exponential space. However, we proved that the problem of comparing Petri automata lies in the class ExpSpace-complete.Finally, we studied Nominal Kleene algebras. We realised that existing descriptions of these algebra were not suited to relational semantics of programming languages. We thus modified them accordingly, and doing so uncovered several natural variations of this model. We then studied formally the bridges one could build between these variations, and between the existing model and our new version of it. This study was conducted using the proof assistant Coq
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Algebraic automata theory"

1

Bolesław, Mikołajczak, ed. Algebraic and structural automata theory. Amsterdam: North-Holland Pub. Co., 1991.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

ItÕo, Masami. Algebraic theory of automata and languages. Singapore: World Scientific, 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Algebraic theory of automata and languages. River Edge, N.J: World Scientific, 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Algebraic theory of automata networks: An introduction. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ja, Greenglaz L., and Gvaramija, eds. Algebraic structures in automata and databases theory. Singapore: World Scientific, 1992.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

B, Kudri︠a︡vt︠s︡ev V., Rosenberg I. G. 1939-, Goldstein Martin, and NATO Public Diplomacy Division, eds. Structural theory of automata, semigroups, and universal algebra. Dordrecht: Springer, 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

M, Delorme, and Mazoyer J, eds. Cellular automata: A parallel model. Dordrecht: Kluwer Academic Publishers, 1999.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Graph algebras and automata. New York: Marcel Dekker, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Argentina) Luis Santaló Winter School-CIMPA Research School Topics in Noncommutative Geometry (3rd 2010 Buenos Aires. Topics in noncommutative geometry: Third Luis Santaló Winter School-CIMPA Research School Topics in Noncommutative Geometry, Universidad de Buenos Aires, Buenos Aires, Argentina, July 26-August 6, 2010. Edited by Cortiñas, Guillermo, editor of compilation. Providence, RI: American Mathematical Society, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Jiří, Adámek. Automata and algebras in categories. Dordrecht: Kluwer Academic Publishers, 1990.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Algebraic automata theory"

1

Cadilhac, Michaël, Andreas Krebs, and Pierre McKenzie. "The Algebraic Theory of Parikh Automata." In Algebraic Informatics, 60–73. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40663-8_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Kuich, Werner. "The algebraic equivalent of AFL theory." In Automata, Languages and Programming, 39–50. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-60084-1_61.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Hirvensalo, Mika. "Quantum Automata Theory – A Review." In Algebraic Foundations in Computer Science, 146–67. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-24897-9_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Kuich, Werner. "Why We Need Semirings in Automata Theory (Extended Abstract)." In Algebraic Informatics, 43–44. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-23021-4_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Deng, Yuxin, and Davide Sangiorgi. "Towards an Algebraic Theory of Typed Mobile Processes." In Automata, Languages and Programming, 445–56. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-27836-8_39.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Dubourg, Etienne, and David Janin. "Algebraic Tools for the Overlapping Tile Product." In Language and Automata Theory and Applications, 335–46. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-04921-2_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Stark, Eugene W., Rance Cleaveland, and Scott A. Smolka. "A Process-Algebraic Language for Probabilistic I/O Automata." In CONCUR 2003 - Concurrency Theory, 193–207. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-45187-7_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Egri-Nagy, Attila, and Chrystopher L. Nehaniv. "Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn-Rhodes Theory." In Implementation and Application of Automata, 315–16. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/978-3-540-30500-2_32.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Piedeleu, Robin, and Fabio Zanasi. "A String Diagrammatic Axiomatisation of Finite-State Automata." In Lecture Notes in Computer Science, 469–89. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-71995-1_24.

Full text
Abstract:
AbstractWe develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite— a result which is provably impossible for the one-dimensional syntax of regular expressions. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.
APA, Harvard, Vancouver, ISO, and other styles
10

Bojańczyk, Mikołaj. "Algebra for trees." In Handbook of Automata Theory, 801–38. Zuerich, Switzerland: European Mathematical Society Publishing House, 2021. http://dx.doi.org/10.4171/automata-1/22.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Algebraic automata theory"

1

Zafar, Nazir Ahmad, Ajmal Hussain, and Amir Ali. "Construction of Morphisms over Extended Algebraic Automata Using Z." In 2008 International Conference on Advanced Computer Theory and Engineering (ICACTE). IEEE, 2008. http://dx.doi.org/10.1109/icacte.2008.186.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Sheng, Ying, Yoni Zohar, Christophe Ringeissen, Jane Lange, Pascal Fontaine, and Clark Barrett. "Politeness for the Theory of Algebraic Datatypes (Extended Abstract)." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/660.

Full text
Abstract:
Algebraic datatypes, and among them lists and trees, have attracted a lot of interest in automated reasoning and Satisfiability Modulo Theories (SMT). Since its latest stable version, the SMT-LIB standard defines a theory of algebraic datatypes, which is currently supported by several mainstream SMT solvers. In this paper, we study this particular theory of datatypes and prove that it is strongly polite, showing also how it can be combined with other arbitrary disjoint theories using polite combination. Our results cover both inductive and finite datatypes, as well as their union. The combination method uses a new, simple, and natural notion of additivity, that enables deducing strong politeness from (weak) politeness.
APA, Harvard, Vancouver, ISO, and other styles
3

Wang, Wenli, Lili Zhang, Chaoyong Jin, Zhenyou Wang, and Yinhe Wang. "Teaching Elementary Linear Algebra for Automatic Control Theory." In 2019 Chinese Control Conference (CCC). IEEE, 2019. http://dx.doi.org/10.23919/chicc.2019.8865209.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Sadjadi, Firooz. "Algebraic invariants and their use in automatic image recognition." In Optics & Photonics 2005, edited by Bahram Javidi and Demetri Psaltis. SPIE, 2005. http://dx.doi.org/10.1117/12.619916.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Jorabchi, Kavous, Joshua Danczyk, and Krishnan Suresh. "Shape Optimization of Potentially Slender Structures." In ASME 2008 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2008. http://dx.doi.org/10.1115/detc2008-50001.

Full text
Abstract:
Shape optimization lies at the heart of modern engineering design. Through shape optimization, computers can, in theory, ‘synthesize’ engineering artifacts in a fully automated fashion. However, a serious limitation today is that the evolving geometry (during optimization) may become slender, i.e., beam or plate-like. Under such circumstances, modern 3-D computational methods, such as finite element analysis (FEA), will fail miserably, and so will the shape optimization process. Indeed, the recommended method for analyzing slender artifacts is to replace them with 1-D beams/ 2-D plates, prior to discretization and computational analysis, a process referred to as geometric dimensional reduction. Unfortunately explicit geometric reduction is impractical and hard to automate during optimization since one cannot predict a priori when an artifact will become slender. In this paper, we develop an implicit dimensional reduction method where the reduction is achieved through an algebraic process. The proposed method of reduction is computationally equivalent to explicit geometric reduction for comparable computational cost. However, the proposed method can be easily automated and integrated within a shape optimization process, and standard off-the-shelf 3-D finite element packages can be used to implement the proposed methodology.
APA, Harvard, Vancouver, ISO, and other styles
6

Adams, A. A., H. Gottliebsen, S. A. Linton, and U. Martin. "Automated theorem proving in support of computer algebra." In the 1999 international symposium. New York, New York, USA: ACM Press, 1999. http://dx.doi.org/10.1145/309831.309949.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Nassopoulos, George F. "Duality, uniqueness of topology and automatic continuity of *-homomorphisms in bornological locally C*-algebras." In Topological Algebras, their Applications, and Related Topics. Warsaw: Institute of Mathematics Polish Academy of Sciences, 2005. http://dx.doi.org/10.4064/bc67-0-23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

LI, HONGBO, and YIHONG WU. "AUTOMATED THEOREM PROVING IN PROJECTIVE GEOMETRY WITH BRACKET ALGEBRA." In Proceedings of the Fourth Asian Symposium (ASCM 2000). WORLD SCIENTIFIC, 2000. http://dx.doi.org/10.1142/9789812791962_0017.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Sun, Frederick, and Jonathan B. Hopkins. "Mobility Analysis of Interconnected Hybrid Flexure Systems Using Screw Algebra and Graph Theory." In ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/detc2016-59206.

Full text
Abstract:
This paper introduces a general method for determining the mobility analysis of flexure systems of any complexity, including those that can’t be broken into parallel and serial flexure subsystems. Such systems are called interconnected hybrid flexure systems because they possess limbs with intermediate bodies that are connected by flexure systems or elements. The method in this paper utilizes screw algebra and graph theory to enable designers to determine the freedom spaces (i.e., the geometric shapes that represent all the ways a body is permitted to move) for all the bodies joined together by compliant flexure elements within interconnected hybrid flexure systems. Although many flexure-based precision motion stages, compliant mechanisms, and microarchitectured materials possess topologies that are highly interconnected, the theory for performing a mobility analysis of such interconnected flexure systems using traditional screw theory does not currently exist. The theory introduced here lays the foundation for an automated tool that can rapidly generate the freedom spaces of every rigid body within a general flexure system without having to perform traditional computationally expensive finite element analysis. Case studies are provided in the paper to demonstrate the utility of the proposed theory.
APA, Harvard, Vancouver, ISO, and other styles
10

Srinivas, Y. L., and Debasish Dutta. "Blending and Joining Using Cyclides." In ASME 1992 Design Technical Conferences. American Society of Mechanical Engineers, 1992. http://dx.doi.org/10.1115/detc1992-0170.

Full text
Abstract:
Abstract We consider the use of cyclides in geometric modeling. These are algebraic surfaces of degree four with interesting properties such as rational parametric forms and closure under offsets. The incorporation of cyclides as primitives in solid modellers will increase their geometric coverage. In this paper, we describe the cyclide and discuss two applications of its use in computer aided design — modeling blending surfaces and the automatic joining of pipes. Implemented examples are also included.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Algebraic automata theory"

1

Borgwardt, Stefan, and Rafael Peñaloza. Complementation and Inclusion of Weighted Automata on Infinite Trees: Revised Version. Technische Universität Dresden, 2011. http://dx.doi.org/10.25368/2022.180.

Full text
Abstract:
Weighted automata can be seen as a natural generalization of finite state automata to more complex algebraic structures. The standard reasoning tasks for unweighted automata can also be generalized to the weighted setting. In this report we study the problems of intersection, complementation, and inclusion for weighted automata on infinite trees and show that they are not harder complexity-wise than reasoning with unweighted automata. We also present explicit methods for solving these problems optimally.
APA, Harvard, Vancouver, ISO, and other styles
2

Borgwardt, Stefan, and Rafael Peñaloza. Complementation and Inclusion of Weighted Automata on Infinite Trees. Technische Universität Dresden, 2010. http://dx.doi.org/10.25368/2022.178.

Full text
Abstract:
Weighted automata can be seen as a natural generalization of finite state automata to more complex algebraic structures. The standard reasoning tasks for unweighted automata can also be generalized to the weighted setting. In this report we study the problems of intersection, complementation and inclusion for weighted automata on infinite trees and show that they are not harder than reasoning with unweighted automata. We also present explicit methods for solving these problems optimally.
APA, Harvard, Vancouver, ISO, and other styles
3

Bach, Christian Friis, and Ken Pearson. Implementing Quotas in GTAP Using GEMPACK or How to Linearize an Inequality. GTAP Technical Paper, September 2000. http://dx.doi.org/10.21642/gtap.tp04.

Full text
Abstract:
The methods described in the paper below have been automated as part of Release 8.0 of GEMPACK. This new version of GEMPACK (which is being beta tested by several modellers now and will be officially released later in 2002) makes it very easy to implement quotas (including import/export quotas and tariff rate quotas). This means that many of the implementation details in the technical paper below are no longer required. To implement quotas etc in GEMPACK, please follow the methodology documented in chapter 16 of GEMPACK User documentation GPD-3, which you can find at http://www.copsmodels.com/gpdoc.htm. If unsure, please contact support@gempack.com.au. 1996, September. This document describes how explicit import and export quotas can be implemented and solved in the GTAP CGE trade model. The techniques described here apply equally well to other general and partial equilibrium models implemented and solved using the GEMPACK software. They also generalise to procedures for handling other inequalities in models solved via GEMPACK (even though GEMPACK does not allow explicit inequalities in the algebraic representation of models). In this document we review some recent applications of GTAP in which explicit import and export quotas have been modelled, and discuss how important it was for these applications to have explicit treatment of quotas. Accompanying this document are various computer files containing the ingredients of examples that readers can carry out for themselves while reading this paper. These files can also be used as a starting point for those who wish to explicitly model quotas in their own models.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Algebraic automata theory' for particular source types:
Journal articles Dissertations / Theses Books
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!

To the bibliography