Infinite String Rewrite Systems and Complexity
Identifieur interne : 002B35 ( Istex/Curation ); précédent : 002B34; suivant : 002B36Infinite String Rewrite Systems and Complexity
Auteurs : Jean-Camille Birget [États-Unis]Source :
- Journal of Symbolic Computation [ 0747-7171 ] ; 1998.
English descriptors
- Teeft :
- Academic press, Algebraic, Algorithm, Alphabet, Bauer, Birget, Boundary label, Cambridge university press, Combinatorial group theory, Complete presentation, Complexity, Complexity bounds, Complexity class, Comput, Computation, Congruence class, Crev, Decidable, Decidable word problem, Derivation, Derivation distance, Derivation work, Deterministic, Deterministic complexity, Deterministic languages, Deterministic polynomial time, Deterministic sequential machine, Deterministic time, Deterministic turing machine, Embeddable, Embedding, Empty word, Enumerable, Greedy derivation, Group presentation, Grzegorczyk hierarchy, Higman, History tape, Homomorphism, Hopcroft, Input alphabet, Input side, Isoperimetric, Isoperimetric function, Kampen, Kampen diagram, Kampen diagrams, Linear time, Madlener, Monoid, Monoid presentation, Monoids, More details, Nite, Nite alphabet, Nite transducer, Nitely, Nondeterministic, Nondeterministic complexity, Other hand, Other tapes, Otto, Outer boundary, Partial function, Precedence graph, Present paper, Rational subset, Recursively, Recursively enumerable, Recursively enumerable word problem, Reduction order, Regular language, Representative function, Representative functions, Right pointer, Rubber tapes, Search phase, Semigroup, Semigroup diagram, Semigroup presentation, Semigroup presentations, Semigroups, Sequential, Space complexity, State symbol, Subsegments, Subset, Tape conversion, Time complexity, Total function, Total time, Total work, Turing, Turing machine, Turing machines, Ullman, Word problem, Word problems, Work distance.
Abstract
Abstract: We study the relation between time complexity and derivation work for the word problem of infinitely presented semigroups and groups. We introduce the notion of theworkof a derivation (defined as the sum of the lengths of all the rules used in the derivation, with multiplicity). The following results are proved:
Url:
DOI: 10.1006/jsco.1997.0198
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :002B72
Links to Exploration step
ISTEX:B81A91E2C72A6DE136E04155B33B25C4A6945EFELe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Infinite String Rewrite Systems and Complexity</title>
<author><name sortKey="Birget, Jean Camille" sort="Birget, Jean Camille" uniqKey="Birget J" first="Jean-Camille" last="Birget">Jean-Camille Birget</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, University of Nebraska, Lincoln, NE, 68588, U.S.A.</mods:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, University of Nebraska, Lincoln, NE, 68588</wicri:regionArea>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:B81A91E2C72A6DE136E04155B33B25C4A6945EFE</idno>
<date when="1998" year="1998">1998</date>
<idno type="doi">10.1006/jsco.1997.0198</idno>
<idno type="url">https://api.istex.fr/ark:/67375/6H6-Z2JHVJM8-R/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002B72</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002B72</idno>
<idno type="wicri:Area/Istex/Curation">002B35</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Infinite String Rewrite Systems and Complexity</title>
<author><name sortKey="Birget, Jean Camille" sort="Birget, Jean Camille" uniqKey="Birget J" first="Jean-Camille" last="Birget">Jean-Camille Birget</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, University of Nebraska, Lincoln, NE, 68588, U.S.A.</mods:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, University of Nebraska, Lincoln, NE, 68588</wicri:regionArea>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Journal of Symbolic Computation</title>
<title level="j" type="abbrev">YJSCO</title>
<idno type="ISSN">0747-7171</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1998">1998</date>
<biblScope unit="volume">25</biblScope>
<biblScope unit="issue">6</biblScope>
<biblScope unit="page" from="759">759</biblScope>
<biblScope unit="page" to="793">793</biblScope>
</imprint>
<idno type="ISSN">0747-7171</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0747-7171</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Academic press</term>
<term>Algebraic</term>
<term>Algorithm</term>
<term>Alphabet</term>
<term>Bauer</term>
<term>Birget</term>
<term>Boundary label</term>
<term>Cambridge university press</term>
<term>Combinatorial group theory</term>
<term>Complete presentation</term>
<term>Complexity</term>
<term>Complexity bounds</term>
<term>Complexity class</term>
<term>Comput</term>
<term>Computation</term>
<term>Congruence class</term>
<term>Crev</term>
<term>Decidable</term>
<term>Decidable word problem</term>
<term>Derivation</term>
<term>Derivation distance</term>
<term>Derivation work</term>
<term>Deterministic</term>
<term>Deterministic complexity</term>
<term>Deterministic languages</term>
<term>Deterministic polynomial time</term>
<term>Deterministic sequential machine</term>
<term>Deterministic time</term>
<term>Deterministic turing machine</term>
<term>Embeddable</term>
<term>Embedding</term>
<term>Empty word</term>
<term>Enumerable</term>
<term>Greedy derivation</term>
<term>Group presentation</term>
<term>Grzegorczyk hierarchy</term>
<term>Higman</term>
<term>History tape</term>
<term>Homomorphism</term>
<term>Hopcroft</term>
<term>Input alphabet</term>
<term>Input side</term>
<term>Isoperimetric</term>
<term>Isoperimetric function</term>
<term>Kampen</term>
<term>Kampen diagram</term>
<term>Kampen diagrams</term>
<term>Linear time</term>
<term>Madlener</term>
<term>Monoid</term>
<term>Monoid presentation</term>
<term>Monoids</term>
<term>More details</term>
<term>Nite</term>
<term>Nite alphabet</term>
<term>Nite transducer</term>
<term>Nitely</term>
<term>Nondeterministic</term>
<term>Nondeterministic complexity</term>
<term>Other hand</term>
<term>Other tapes</term>
<term>Otto</term>
<term>Outer boundary</term>
<term>Partial function</term>
<term>Precedence graph</term>
<term>Present paper</term>
<term>Rational subset</term>
<term>Recursively</term>
<term>Recursively enumerable</term>
<term>Recursively enumerable word problem</term>
<term>Reduction order</term>
<term>Regular language</term>
<term>Representative function</term>
<term>Representative functions</term>
<term>Right pointer</term>
<term>Rubber tapes</term>
<term>Search phase</term>
<term>Semigroup</term>
<term>Semigroup diagram</term>
<term>Semigroup presentation</term>
<term>Semigroup presentations</term>
<term>Semigroups</term>
<term>Sequential</term>
<term>Space complexity</term>
<term>State symbol</term>
<term>Subsegments</term>
<term>Subset</term>
<term>Tape conversion</term>
<term>Time complexity</term>
<term>Total function</term>
<term>Total time</term>
<term>Total work</term>
<term>Turing</term>
<term>Turing machine</term>
<term>Turing machines</term>
<term>Ullman</term>
<term>Word problem</term>
<term>Word problems</term>
<term>Work distance</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We study the relation between time complexity and derivation work for the word problem of infinitely presented semigroups and groups. We introduce the notion of theworkof a derivation (defined as the sum of the lengths of all the rules used in the derivation, with multiplicity). The following results are proved:</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002B35 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 002B35 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:B81A91E2C72A6DE136E04155B33B25C4A6945EFE |texte= Infinite String Rewrite Systems and Complexity }}
This area was generated with Dilib version V0.6.33. |