On the k-reversibility of finite automata

dc.contributor.authorFalucskai, János
dc.date.accessioned2012-02-23T12:18:24Z
dc.date.available2012-02-23T12:18:24Z
dc.date.issued2012-02-23
dc.date.year2009-12-29
dc.description.abstractIt is a famous result of Angluin (1982 [1]) that there exists a time polynomial and space linear algorithm to identify the canonical automata of k- reversible languages by using characteristic sample sets. This result has several applications. In this paper we characterise the class of all automata for which her method is not applicable. In particular, the aim of this paper is to characterise the family of finite automata which are not k-reversible for any non-negative integer k.en_US
dc.format.firstpage71en_US
dc.format.issue1en_US
dc.format.lastpage75en_US
dc.format.pages5en_US
dc.format.volume36en_US
dc.identifier.urihttp://hdl.handle.net/123456789/15
dc.language.isoenen_US
dc.subjectfinite automataen_US
dc.subjectk-reversible automataen_US
dc.titleOn the k-reversibility of finite automataen_US
dc.title.journalAnnales Mathematicae et Informaticaeen_US
dc.type.classArticleen_US
dc.type.specificationScientificen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
AMI_36_from71to75.pdf
Size:
112.84 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
2.57 KB
Format:
Item-specific license agreed upon to submission
Description: