6533b872fe1ef96bd12d2c5a

RESEARCH PRODUCT

Tally languages accepted by Monte Carlo pushdown automata

Dainis GeidmanisRusins FreivaldsJanis Kaneps

subject

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordTheoretical computer scienceComputational complexity theoryComputer scienceDeterministic pushdown automatonTuring machinesymbols.namesakeRegular languageComputer Science::Logic in Computer ScienceQuantum finite automataNondeterministic finite automatonDiscrete mathematicsFinite-state machineDeterministic context-free languageComputabilityDeterministic context-free grammarContext-free languagePushdown automatonAbstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Cone (formal languages)Embedded pushdown automatonUndecidable problemNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonsymbolsComputer Science::Programming LanguagesAlphabetComputer Science::Formal Languages and Automata Theory

description

Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.

yearjournalcountryeditionlanguage
1997-01-01
https://doi.org/10.1007/3-540-63248-4_16