Infinite String Rewrite Systems and Complexity
Identifieur interne : 00B359 ( Main/Exploration ); précédent : 00B358; suivant : 00B360Infinite 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
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002B72
- to stream Istex, to step Curation: 002B35
- to stream Istex, to step Checkpoint: 002591
- to stream Main, to step Merge: 00BA81
- to stream Main, to step Curation: 00B359
Le 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></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><idno type="wicri:Area/Istex/Checkpoint">002591</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002591</idno><idno type="wicri:doubleKey">0747-7171:1998:Birget J:infinite:string:rewrite</idno><idno type="wicri:Area/Main/Merge">00BA81</idno><idno type="wicri:Area/Main/Curation">00B359</idno><idno type="wicri:Area/Main/Exploration">00B359</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"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science, University of Nebraska, Lincoln, NE, 68588</wicri:regionArea><wicri:noRegion>68588</wicri:noRegion></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><affiliations><list><country><li>États-Unis</li></country></list><tree><country name="États-Unis"><noRegion><name sortKey="Birget, Jean Camille" sort="Birget, Jean Camille" uniqKey="Birget J" first="Jean-Camille" last="Birget">Jean-Camille Birget</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B359 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00B359 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:B81A91E2C72A6DE136E04155B33B25C4A6945EFE
|texte= Infinite String Rewrite Systems and Complexity
}}
| This area was generated with Dilib version V0.6.33. |  |