On rational solution of the state equation of a finite automaton
We prove that the necessary and sufficient condition for the state equation of a finite automaton M to have a rational solution is that the lexicographical Gödel numbers of the strings belonging to each of the end-sets of M form an ultimately periodic set. A method of determining the existence of a...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
1988-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1155/S0161171288000420 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849411391862079488 |
|---|---|
| author | R. Chaudhuri H. Höft |
| author_facet | R. Chaudhuri H. Höft |
| author_sort | R. Chaudhuri |
| collection | DOAJ |
| description | We prove that the necessary and sufficient condition for the state equation of a finite automaton M to have a rational solution is that the lexicographical Gödel numbers of the strings belonging to each of the end-sets of M form an ultimately periodic set. A method of determining the existence of a rational solution of the state equation is also given. |
| format | Article |
| id | doaj-art-66c36215a47b482eb8bcc72640bfab71 |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 1988-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-66c36215a47b482eb8bcc72640bfab712025-08-20T03:34:47ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04251988-01-0111235536410.1155/S0161171288000420On rational solution of the state equation of a finite automatonR. Chaudhuri0H. Höft1Department of Computer Science, Eastern Michigan University, Ypsilanti 48197, MI, USADepartment of Computer Science, Eastern Michigan University, Ypsilanti 48197, MI, USAWe prove that the necessary and sufficient condition for the state equation of a finite automaton M to have a rational solution is that the lexicographical Gödel numbers of the strings belonging to each of the end-sets of M form an ultimately periodic set. A method of determining the existence of a rational solution of the state equation is also given.http://dx.doi.org/10.1155/S0161171288000420automatastate equationGF(2)rational solutions. |
| spellingShingle | R. Chaudhuri H. Höft On rational solution of the state equation of a finite automaton International Journal of Mathematics and Mathematical Sciences automata state equation GF(2) rational solutions. |
| title | On rational solution of the state equation of a finite automaton |
| title_full | On rational solution of the state equation of a finite automaton |
| title_fullStr | On rational solution of the state equation of a finite automaton |
| title_full_unstemmed | On rational solution of the state equation of a finite automaton |
| title_short | On rational solution of the state equation of a finite automaton |
| title_sort | on rational solution of the state equation of a finite automaton |
| topic | automata state equation GF(2) rational solutions. |
| url | http://dx.doi.org/10.1155/S0161171288000420 |
| work_keys_str_mv | AT rchaudhuri onrationalsolutionofthestateequationofafiniteautomaton AT hhoft onrationalsolutionofthestateequationofafiniteautomaton |