UnivTrevesV1, Main, Merge, bibRecord, 001530

Decidability of code properties

Identifieur interne : 001530 ( Main/Merge ); précédent : 001529; suivant : 001531

Decidability of code properties

Auteurs : Henning Fernau [Allemagne] ; Klaus Reinhardt [Allemagne] ; Ludwig Staiger [Allemagne]

Source :

Informatique théorique et applications : (Imprimé) [ 0988-3754 ] ; 2007.

RBID : Pascal:08-0192943

Descripteurs français

Pascal (Inist)
- Décidabilité, Indécidabilité, Retard, Suffixe, Automate fini, Code préfixe, Informatique théorique, Application, Code suffixe, Langage L, Préfixe.

English descriptors

KwdEn :
- Application, Computer theory, Decidability, Delay, Finite automaton, Prefix code, Suffix, Undecidability.

Abstract

We explore the borderline between decidability and undecidability of the following question: "Let C be a class of codes. Given a machine R of type X, is it decidable whether the language L(m) lies in C or not?" for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000840
to stream PascalFrancis, to step Curation: 000595
to stream PascalFrancis, to step Checkpoint: 000700

Links to Exploration step

Pascal:08-0192943

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Decidability of code properties</title>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Fachbereich IV, Abteilung Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>Universität Trier</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
<author><name sortKey="Reinhardt, Klaus" sort="Reinhardt, Klaus" uniqKey="Reinhardt K" first="Klaus" last="Reinhardt">Klaus Reinhardt</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Wilhelm-Schickard-Institut für Informatik, Universität Tiibingen, Sand 13</s1>
<s2>72076 Tübingen</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<placeName><region type="land" nuts="1">Bade-Wurtemberg</region>
<region type="district" nuts="2">District de Tübingen</region>
<settlement type="city">Tübingen</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Staiger, Ludwig" sort="Staiger, Ludwig" uniqKey="Staiger L" first="Ludwig" last="Staiger">Ludwig Staiger</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Institut für Informatik, Martin -Luther-Universität Halle-Wittenberg, von-Seckendorff-Platz 1</s1>
<s2>06099 Halle</s2>
<s3>DEU</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>06099 Halle</wicri:noRegion>
<wicri:noRegion>von-Seckendorff-Platz 1</wicri:noRegion>
<wicri:noRegion>06099 Halle</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">08-0192943</idno>
<date when="2007">2007</date>
<idno type="stanalyst">PASCAL 08-0192943 INIST</idno>
<idno type="RBID">Pascal:08-0192943</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000840</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000595</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000700</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000700</idno>
<idno type="wicri:doubleKey">0988-3754:2007:Fernau H:decidability:of:code</idno>
<idno type="wicri:Area/Main/Merge">001530</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Decidability of code properties</title>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Fachbereich IV, Abteilung Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>Universität Trier</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
<author><name sortKey="Reinhardt, Klaus" sort="Reinhardt, Klaus" uniqKey="Reinhardt K" first="Klaus" last="Reinhardt">Klaus Reinhardt</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Wilhelm-Schickard-Institut für Informatik, Universität Tiibingen, Sand 13</s1>
<s2>72076 Tübingen</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<placeName><region type="land" nuts="1">Bade-Wurtemberg</region>
<region type="district" nuts="2">District de Tübingen</region>
<settlement type="city">Tübingen</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Staiger, Ludwig" sort="Staiger, Ludwig" uniqKey="Staiger L" first="Ludwig" last="Staiger">Ludwig Staiger</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Institut für Informatik, Martin -Luther-Universität Halle-Wittenberg, von-Seckendorff-Platz 1</s1>
<s2>06099 Halle</s2>
<s3>DEU</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>06099 Halle</wicri:noRegion>
<wicri:noRegion>von-Seckendorff-Platz 1</wicri:noRegion>
<wicri:noRegion>06099 Halle</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Informatique théorique et applications : (Imprimé)</title>
<title level="j" type="abbreviated">Inform. théor. appl. : (Imprimé</title>
<idno type="ISSN">0988-3754</idno>
<imprint><date when="2007">2007</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Informatique théorique et applications : (Imprimé)</title>
<title level="j" type="abbreviated">Inform. théor. appl. : (Imprimé</title>
<idno type="ISSN">0988-3754</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Application</term>
<term>Computer theory</term>
<term>Decidability</term>
<term>Delay</term>
<term>Finite automaton</term>
<term>Prefix code</term>
<term>Suffix</term>
<term>Undecidability</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Décidabilité</term>
<term>Indécidabilité</term>
<term>Retard</term>
<term>Suffixe</term>
<term>Automate fini</term>
<term>Code préfixe</term>
<term>Informatique théorique</term>
<term>Application</term>
<term>Code suffixe</term>
<term>Langage L</term>
<term>Préfixe</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We explore the borderline between decidability and undecidability of the following question: "Let C be a class of codes. Given a machine R of type X, is it decidable whether the language L(m) lies in C or not?" for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
</country>
<region><li>Bade-Wurtemberg</li>
<li>District de Tübingen</li>
<li>Rhénanie-Palatinat</li>
</region>
<settlement><li>Trèves (Allemagne)</li>
<li>Tübingen</li>
</settlement>
<orgName><li>Université de Trèves</li>
</orgName>
</list>
<tree><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
</region>
<name sortKey="Reinhardt, Klaus" sort="Reinhardt, Klaus" uniqKey="Reinhardt K" first="Klaus" last="Reinhardt">Klaus Reinhardt</name>
<name sortKey="Staiger, Ludwig" sort="Staiger, Ludwig" uniqKey="Staiger L" first="Ludwig" last="Staiger">Ludwig Staiger</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Merge

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001530 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 001530 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Main
   |étape=   Merge
   |type=    RBID
   |clé=     Pascal:08-0192943
   |texte=   Decidability of code properties
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

Decidability of code properties

Decidability of code properties

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri