Search results for "Undecidable problem"

showing 3 items of 13 documents

Deciding properties of integral relational automata

1994

This paper investigates automated model checking possibilities for CTL* formulae over infinite transition systems represented by relational automata (RA). The general model checking problem for CTL* formulae over RA is shown undecidable, the undecidability being observed already on the class of Restricted CTL formulae. The decidability result, however, is obtained for another substantial subset of the logic, called A-CTL*+, which includes all ”linear time” formulae.

Model checkingDiscrete mathematicsClass (set theory)TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESComputer scienceComputer Science::Software EngineeringDecidabilityUndecidable problemComputer Science::Multiagent SystemsCTL*TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESRelational calculusTheoryofComputation_LOGICSANDMEANINGSOFPROGRAMSComputer Science::Logic in Computer ScienceAutomata theoryTime complexityComputer Science::Formal Languages and Automata Theory
researchProduct

Tally languages accepted by Monte Carlo pushdown automata

1997

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.

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
researchProduct

Some decisional problems on rational relations

1997

Abstract In this paper we prove that the problem of deciding whether a deterministic rational relation is star-free is recursively solvable, although the same problem for any rational relation is undecidable. We also prove that a rational relation is star-free if and only if it is aperiodic and deterministic.

TheoryofComputation_MISCELLANEOUSDiscrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESGeneral Computer ScienceTheoretical Computer ScienceUndecidable problemTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESIf and only ifAperiodic graphComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONAstrophysics::Solar and Stellar AstrophysicsRational relationComputer Science::Formal Languages and Automata TheoryAstrophysics::Galaxy AstrophysicsComputer Science(all)MathematicsTheoretical Computer Science
researchProduct