Search

Your search keyword '"68Q42"' showing total 4 results
Start Over Descriptor "68Q42" Publisher hal ccsd
4 results on '"68Q42"'

1. Coherent Presentations of Monoidal Categories

Author

Curien, Pierre-Louis, Mimram, Samuel, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Design, study and implementation of languages for proofs and programs (PI.R2), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), ANR-13-BS02-0005,CATHRE,Catégories, Homotopie et Réécriture(2013), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)

Subjects
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, 68Q42, Mathematics::Category Theory, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems, FOS: Mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Mathematics - Category Theory, Category Theory (math.CT), F.4.2, Logic in Computer Science (cs.LO), [MATH.MATH-CT]Mathematics [math]/Category Theory [math.CT]
Abstract

International audience; Presentations of categories are a well-known algebraic tool to provide descriptions of categories by means of generators, for objects and morphisms, and relations on morphisms. We generalize here this notion, in order to consider situations where the objects are considered modulo an equivalence relation, which is described by equational generators. When those form a convergent (abstract) rewriting system on objects, there are three very natural constructions that can be used to define the category which is described by the presentation: one consists in turning equational generators into identities (i.e. considering a quotient category), one consists in formally adding inverses to equational generators (i.e. localizing the category), and one consists in restricting to objects which are normal forms. We show that, under suitable coherence conditions on the presentation, the three constructions coincide, thus generalizing celebrated results on presentations of groups, and we extend those conditions to presentations of monoidal categories.

Published
2017
Full Text
View/download PDF

2. Bottom-up rewriting for words and terms

Author

Géraud Sénizergues, Irène Durand, Méthodes Formelles, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Durand, Irène, Sénizergues, Géraud, and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)

Subjects
FOS: Computer and information sciences, Class (set theory), Unary operation, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Accessibility problem, Semi-Thue systems, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Physics::Fluid Dynamics, 68Q42, 03D03, 03D40, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Term rewriting systems, Mathematics, [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Discrete mathematics, Algebra and Number Theory, Linear system, Term (logic), Undecidable problem, Decidability, Computational Mathematics, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], Confluence, MSC 68Q42 03D03 03D40, 2000 MSC: 68Q42, 03D03, 03D40, Rewriting, Regularity preservation
Abstract

For the whole class of linear term rewriting systems, we define \emph{bottom-up rewriting} which is a restriction of the usual notion of rewriting. We show that bottom-up rewriting effectively inverse-preserves recognizability and analyze the complexity of the underlying construction. The Bottom-Up class (BU) is, by definition, the set of linear systems for which every derivation can be replaced by a bottom-up derivation. Membership to BU turns out to be undecidable, we are thus lead to define more restricted classes: the classes SBU(k), k in N of Strongly Bottom-Up(k) systems for which we show that membership is decidable. We define the class of Strongly Bottom-Up systems by SBU = U_{k in \} SBU(k). We give a polynomial sufficient condition for a system to be in $\SBU$. The class SBU contains (strictly) several classes of systems which were already known to inverse preserve recognizability: the inverse left-basic semi-Thue systems (viewed as unary term rewriting systems), the linear growing term rewriting systems, the inverse Linear-Finite-Path-Ordering systems., 86 pages; long version to be cut into pieces for publication

Published
2014
Full Text
View/download PDF

3. Properties of co-operations: diagrammatic proofs

Author

Pierre Rannou, Institut de mathématiques de Luminy (IML), Université de la Méditerranée - Aix-Marseille 2-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-Université de la Méditerranée - Aix-Marseille 2

Subjects
diagram rewriting, Computation, 0102 computer and information sciences, 02 engineering and technology, Mathematical proof, 01 natural sciences, Mathematics (miscellaneous), 68Q42, 08A70, Mathematics::Quantum Algebra, Computer Science::Logic in Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Syntax (programming languages), Diagram, Mathematics::Rings and Algebras, cocommutativity, 16. Peace & justice, Computer Science Applications, Algebra, Diagrammatic reasoning, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, computations in bialgebras, 010201 computation theory & mathematics, Confluence, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Computer Science::Programming Languages, 020201 artificial intelligence & image processing, Rewriting, coassociativity
Abstract

We propose an alternative approach, based on diagram rewriting, for computations in bialgebras. We illustrate this graphical syntax by proving some properties of co-operations, including coassociativity and cocommutativity. This amounts to checking the confluence of some rewriting systems.

Published
2012
Full Text
View/download PDF

4. Higher-dimensional categories with finite derivation type

Author

Yves Guiraud, Philippe Malbos, Formal islands: foundations and applications (PAREO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), This work has been partially supported by ANR INVAL project (ANR-05-BLAN-0267)., ANR-05-BLAN-0267,INVAL,Invariants algébriques des systèmes informatiques(2005), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Institut Camille Jordan (ICJ), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)

Subjects
18D05, 68Q42, 18D10, Mathematics - Category Theory, 18C10, K-Theory and Homology (math.KT), $n$-category, 57M20, low-dimensional topology, rewriting, finite derivation type, Mathematics::Category Theory, [MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT], Mathematics - K-Theory and Homology, FOS: Mathematics, [MATH.MATH-KT]Mathematics [math]/K-Theory and Homology [math.KT], Algebraic Topology (math.AT), Category Theory (math.CT), Mathematics - Algebraic Topology, polygraph, [MATH.MATH-CT]Mathematics [math]/Category Theory [math.CT]
Abstract

International audience; We study convergent (terminating and confluent) presentations of n-categories. Using the notion of polygraph (or computad), we introduce the homotopical property of finite derivation type for $n$-categories, generalizing the one introduced by Squier for word rewriting systems. We characterize this property by using the notion of critical branching. In particular, we define sufficient conditions for an n-category to have finite derivation type. Through examples, we present several techniques based on derivations of 2-categories to study convergent presentations by 3-polygraphs.

Published
2009
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results