Ambiguity by restarting automata

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00004065" target="_blank" >RIV/00216208:11320/07:00004065 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Ambiguity by restarting automata
Original language description
Restarting automata can be considered as a machine model as well as regulated rewriting systems. We introduce a measure of ambiguity for restarting automata which recognizes a language as a projection of its characteristic language (containing also auxiliarynon-inputsymbols) into its input alphabet. Based on this measure we define an ambiguity measure of languages. This measure can be considered as a measure of non-determinism of languages. We show that there is an infinite hierarchy with respect to thedegree of ambiguity even inside linear languages and that there are linear languages with a linear ambiguity.
Czech name
Víceznačnost pomocí restartovacích automatů
Czech description
Restartovací automaty lze studovat jako automaty i jako regulované přepisovací systémy. V práci se zavádí míra víceznačnosti pro restartovací automaty, které rozpoznávají jazyky pomocí projekce z jejich charakteristických jazyků (obsahujících též pomocnésymboly) na jazyky složené pouze ze vstupních symbolů. Na této míře je založena míra víceznačnosti jazyků. Je ukázáno, že tuto míru lze považovat za míru nedeterminismu jazyků. Hlavním výsledkem je důkaz existence nekonečné škály tříd jazyků podle stupně jejich víceznačnosti a existence jazyků s lineární vzrůstem víceznačnosti s ohledem na růst délky jejich vět (slov).

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1ET100300517" target="_blank" >1ET100300517: Methods for Intelligent Systems and Their Applications in Datamining and Natural Language Processing</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)