6533b85afe1ef96bd12b8a91

RESEARCH PRODUCT

Iterative pairs and multitape automata

Stefano VarricchioMarina Madonia

subject

ComputingMilieux_GENERALDiscrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESFinite-state machineAperiodic graphFree monoidDegenerate energy levelsMathematicsAutomaton

description

In this paper we prove that if every iterative k-tuple of a language L recognized by a k-tape automaton is very degenerate, then L is recognizable. Moreover, we prove that if L is an aperiodic langnage recognized by a deterministic k-tape automaton, then L is recognizable.

yearjournalcountryeditionlanguage
1996-01-01
https://doi.org/10.1007/3-540-61064-2_26