On the classification of Post automaton bases by the decidability of the A-completeness property for definite automata

DOI10.1515/DMA.2010.020zbMath1221.03032OpenAlexW1994076373MaRDI QIDQ3585192

Dmitriy N. Zhuk

Publication date: 19 August 2010

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma.2010.020

zbMATH Keywords

undecidabilityBoolean functionsdecidabilityhalting problemdefinite automata\(A\)-completeness problemPost productions

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Thue and Post systems, etc. (03D03)

Related Items (1)

Number of labelings of definite automata graphs

This page was built for publication: On the classification of Post automaton bases by the decidability of the A-completeness property for definite automata