Decidability of Skolem matrix emptiness problem entails constructability of exact regular expression
From MaRDI portal
Publication:1171048
DOI10.1016/0304-3975(82)90134-7zbMath0498.03008MaRDI QIDQ1171048
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90134-7
exact algorithm; recursiveness; equivalence problem modulo finite set; full matrix equivalence problem; integer-valued square matrix
03D35: Undecidability and degrees of sets of sentences
68T99: Artificial intelligence
03B25: Decidability of theories and sets of sentences
Cites Work
- Unnamed Item
- Unnamed Item
- What makes some language theory problems undecidable
- On a Theorem of R. Jungen
- Deux propriétés décidables des suites récurrentes linéaires
- Fuzzy events realized by finite probabilistic automata
- Mappings induced by PGSM-mappings and some recursively unsolvable problems of finite probabilistic automata
- On stochastic languages