Complexity Measures for Language Recognition by Canonic Systems
A canonic system C is a specification of a recursively enumerable set, such as a set of strings over a finite alphabet. From this description C, it is possible to generate a system C , called a proof measure function, which is an indication of the complexity of the language defined. For certain sim...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149394 |
| _version_ | 1811073043061014528 |
|---|---|
| author | Haggerty, Joseph P. |
| author_facet | Haggerty, Joseph P. |
| author_sort | Haggerty, Joseph P. |
| collection | MIT |
| description | A canonic system C is a specification of a recursively enumerable set, such as a set of strings over a finite alphabet. From this description C, it is possible to generate a system C , called a proof measure function, which is an indication of the complexity of the language defined. For certain simple but important classes of canonic system, algebraic bounds on these functions can be derived from the structure of the system. |
| first_indexed | 2024-09-23T09:27:42Z |
| id | mit-1721.1/149394 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:27:42Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1493942023-03-30T04:11:49Z Complexity Measures for Language Recognition by Canonic Systems Haggerty, Joseph P. A canonic system C is a specification of a recursively enumerable set, such as a set of strings over a finite alphabet. From this description C, it is possible to generate a system C , called a proof measure function, which is an indication of the complexity of the language defined. For certain simple but important classes of canonic system, algebraic bounds on these functions can be derived from the structure of the system. 2023-03-29T14:55:16Z 2023-03-29T14:55:16Z 1970-10 https://hdl.handle.net/1721.1/149394 04072634 MIT-LCS-TR-077 MAC-TR-077 application/pdf |
| spellingShingle | Haggerty, Joseph P. Complexity Measures for Language Recognition by Canonic Systems |
| title | Complexity Measures for Language Recognition by Canonic Systems |
| title_full | Complexity Measures for Language Recognition by Canonic Systems |
| title_fullStr | Complexity Measures for Language Recognition by Canonic Systems |
| title_full_unstemmed | Complexity Measures for Language Recognition by Canonic Systems |
| title_short | Complexity Measures for Language Recognition by Canonic Systems |
| title_sort | complexity measures for language recognition by canonic systems |
| url | https://hdl.handle.net/1721.1/149394 |
| work_keys_str_mv | AT haggertyjosephp complexitymeasuresforlanguagerecognitionbycanonicsystems |