A canonical automaton for one-rule length-preserving string rewrite systems

In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a letter-to-letter transducer that computes the relation induced by a one-rule lengt...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2015-10, Vol.244 (244), p.203-228
Main Authors: Latteux, Michel, Roos, Yves
Format: Article
Language:English
Subjects:
Computer Science
Formal Languages and Automata Theory
Rational transduction
String rewrite system
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c398t-37d34de4e33e56f35a7cda52fed3f0cd148c3706d34781c2e21fedc80c71eff73
cites cdi_FETCH-LOGICAL-c398t-37d34de4e33e56f35a7cda52fed3f0cd148c3706d34781c2e21fedc80c71eff73
container_end_page 228
container_issue 244
container_start_page 203
container_title Information and computation
container_volume 244
creator Latteux, Michel
Roos, Yves
description In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a letter-to-letter transducer that computes the relation induced by a one-rule length-preserving string rewrite system. This transducer can be seen as an automaton over an alphabet A×A. We prove that this automaton is finite if and only if the corresponding relation is rational. We also identify a sufficient condition for the context-freeness of the language L recognized by this automaton and, when this condition is satisfied, we construct a pushdown automaton that recognizes L.
doi_str_mv 10.1016/j.ic.2015.07.002
format article
fullrecord <record><control><sourceid>elsevier_hal_p</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_hal_01205202v1</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0890540115000796</els_id><sourcerecordid>S0890540115000796</sourcerecordid><originalsourceid>FETCH-LOGICAL-c398t-37d34de4e33e56f35a7cda52fed3f0cd148c3706d34781c2e21fedc80c71eff73</originalsourceid><addsrcrecordid>eNp1kDFPwzAQhS0EEqWwM2ZlSLiz4zhlqyqgiEosMFuWc2ldpXFlu0X99yQqYmN6p7v3nfQeY_cIBQJWj9vC2YIDygJUAcAv2ARhBjmvJF6yCdTDLEvAa3YT4xYAUZbVhL3PM2t63ztruswckt-Z5Pus9SHzPeXh0FHWUb9Om3wfKFI4un6dxRRGCfQdXKIsnmKiXbxlV63pIt396pR9vTx_Lpb56uP1bTFf5VbM6pQL1YiyoZKEIFm1QhplGyN5S41owTZY1lYoqAaXqtFy4jicbA1WIbWtElP2cP67MZ3eB7cz4aS9cXo5X-lxB8hBcuBHHLxw9trgYwzU_gEIeixOb7WzeixOg9JDcQPydEZoyHB0FHS0jnpLjQtkk268-x_-AbYwdd0</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>A canonical automaton for one-rule length-preserving string rewrite systems</title><source>ScienceDirect Freedom Collection</source><creator>Latteux, Michel ; Roos, Yves</creator><creatorcontrib>Latteux, Michel ; Roos, Yves</creatorcontrib><description>In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a letter-to-letter transducer that computes the relation induced by a one-rule length-preserving string rewrite system. This transducer can be seen as an automaton over an alphabet A×A. We prove that this automaton is finite if and only if the corresponding relation is rational. We also identify a sufficient condition for the context-freeness of the language L recognized by this automaton and, when this condition is satisfied, we construct a pushdown automaton that recognizes L.</description><identifier>ISSN: 0890-5401</identifier><identifier>EISSN: 1090-2651</identifier><identifier>DOI: 10.1016/j.ic.2015.07.002</identifier><language>eng</language><publisher>Elsevier Inc</publisher><subject>Computer Science ; Formal Languages and Automata Theory ; Rational transduction ; String rewrite system</subject><ispartof>Information and computation, 2015-10, Vol.244 (244), p.203-228</ispartof><rights>2015 Elsevier Inc.</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c398t-37d34de4e33e56f35a7cda52fed3f0cd148c3706d34781c2e21fedc80c71eff73</citedby><cites>FETCH-LOGICAL-c398t-37d34de4e33e56f35a7cda52fed3f0cd148c3706d34781c2e21fedc80c71eff73</cites><orcidid>0000-0002-5045-4399</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,776,780,881,27903,27904</link.rule.ids><backlink>$$Uhttps://hal.science/hal-01205202$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Latteux, Michel</creatorcontrib><creatorcontrib>Roos, Yves</creatorcontrib><title>A canonical automaton for one-rule length-preserving string rewrite systems</title><title>Information and computation</title><description>In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a letter-to-letter transducer that computes the relation induced by a one-rule length-preserving string rewrite system. This transducer can be seen as an automaton over an alphabet A×A. We prove that this automaton is finite if and only if the corresponding relation is rational. We also identify a sufficient condition for the context-freeness of the language L recognized by this automaton and, when this condition is satisfied, we construct a pushdown automaton that recognizes L.</description><subject>Computer Science</subject><subject>Formal Languages and Automata Theory</subject><subject>Rational transduction</subject><subject>String rewrite system</subject><issn>0890-5401</issn><issn>1090-2651</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNp1kDFPwzAQhS0EEqWwM2ZlSLiz4zhlqyqgiEosMFuWc2ldpXFlu0X99yQqYmN6p7v3nfQeY_cIBQJWj9vC2YIDygJUAcAv2ARhBjmvJF6yCdTDLEvAa3YT4xYAUZbVhL3PM2t63ztruswckt-Z5Pus9SHzPeXh0FHWUb9Om3wfKFI4un6dxRRGCfQdXKIsnmKiXbxlV63pIt396pR9vTx_Lpb56uP1bTFf5VbM6pQL1YiyoZKEIFm1QhplGyN5S41owTZY1lYoqAaXqtFy4jicbA1WIbWtElP2cP67MZ3eB7cz4aS9cXo5X-lxB8hBcuBHHLxw9trgYwzU_gEIeixOb7WzeixOg9JDcQPydEZoyHB0FHS0jnpLjQtkk268-x_-AbYwdd0</recordid><startdate>20151001</startdate><enddate>20151001</enddate><creator>Latteux, Michel</creator><creator>Roos, Yves</creator><general>Elsevier Inc</general><general>Elsevier</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>1XC</scope><orcidid>https://orcid.org/0000-0002-5045-4399</orcidid></search><sort><creationdate>20151001</creationdate><title>A canonical automaton for one-rule length-preserving string rewrite systems</title><author>Latteux, Michel ; Roos, Yves</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c398t-37d34de4e33e56f35a7cda52fed3f0cd148c3706d34781c2e21fedc80c71eff73</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Computer Science</topic><topic>Formal Languages and Automata Theory</topic><topic>Rational transduction</topic><topic>String rewrite system</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Latteux, Michel</creatorcontrib><creatorcontrib>Roos, Yves</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><collection>Hyper Article en Ligne (HAL)</collection><jtitle>Information and computation</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Latteux, Michel</au><au>Roos, Yves</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A canonical automaton for one-rule length-preserving string rewrite systems</atitle><jtitle>Information and computation</jtitle><date>2015-10-01</date><risdate>2015</risdate><volume>244</volume><issue>244</issue><spage>203</spage><epage>228</epage><pages>203-228</pages><issn>0890-5401</issn><eissn>1090-2651</eissn><abstract>In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a letter-to-letter transducer that computes the relation induced by a one-rule length-preserving string rewrite system. This transducer can be seen as an automaton over an alphabet A×A. We prove that this automaton is finite if and only if the corresponding relation is rational. We also identify a sufficient condition for the context-freeness of the language L recognized by this automaton and, when this condition is satisfied, we construct a pushdown automaton that recognizes L.</abstract><pub>Elsevier Inc</pub><doi>10.1016/j.ic.2015.07.002</doi><tpages>26</tpages><orcidid>https://orcid.org/0000-0002-5045-4399</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0890-5401
ispartof Information and computation, 2015-10, Vol.244 (244), p.203-228
issn 0890-5401
1090-2651
language eng
recordid cdi_hal_primary_oai_HAL_hal_01205202v1
source ScienceDirect Freedom Collection
subjects Computer Science
Formal Languages and Automata Theory
Rational transduction
String rewrite system
title A canonical automaton for one-rule length-preserving string rewrite systems
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-26T02%3A44%3A48IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-elsevier_hal_p&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20canonical%20automaton%20for%20one-rule%20length-preserving%20string%20rewrite%20systems&rft.jtitle=Information%20and%20computation&rft.au=Latteux,%20Michel&rft.date=2015-10-01&rft.volume=244&rft.issue=244&rft.spage=203&rft.epage=228&rft.pages=203-228&rft.issn=0890-5401&rft.eissn=1090-2651&rft_id=info:doi/10.1016/j.ic.2015.07.002&rft_dat=%3Celsevier_hal_p%3ES0890540115000796%3C/elsevier_hal_p%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c398t-37d34de4e33e56f35a7cda52fed3f0cd148c3706d34781c2e21fedc80c71eff73%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true