Actualmente estoy haciendo una investigación de lenguaje formal que involucra clases de idiomas por encima de Regular pero debajo de Context Free. Estoy viendo cosas como máquinas multicontadores limitados por inversión, máquinas de contador de una sola pila, CFL deterministas, etc.
Me pregunto si alguien sabe de un buen libro o encuesta que describa las propiedades de estos idiomas. La mayor parte de lo que estoy viendo es demasiado oscuro o demasiado nuevo para estar en mi libro Hopcroft-Ullman, incluso la edición de 1979.
Principalmente, estoy buscando qué clases de idiomas están contenidas entre sí, las propiedades de cierre de estos idiomas y la capacidad de resolución de los problemas básicos (problemas F) en estos idiomas.
Algunos ejemplos de cosas que buscaría en esta referencia:
- ¿Todos los idiomas son aceptados por las máquinas de contadores múltiples con límite de inversión también aceptadas por las máquinas de contador único sin límites de inversión?
- ¿Están cerrados los lenguajes deterministas de MultiCounter con inversión inversa bajo concatenación izquierda y derecha?
- Es la universalidad decidible para máquinas de un solo contador.
Estas son solo preguntas de ejemplo, tengo muchas otras que surgen en mi trabajo diario.
Como punto de partida, he intentado rastrear qué documentos citan "Máquinas multicounter y sus decisiones" de Oscar Ibarra, pero no he encontrado mucho.
Respuestas:
No temas estándar, no. Y lo siento, no tengo una visión general.
Sin embargo, echaría un vistazo a la tesis doctoral de Klaus Reinhardt para al menos una imagen de las diversas familias que viven en esta área. Vea la página 64 para un diagrama del zoológico. Motivado por redes de Petri con arcos inhibidores, Reinhardt estudia multicontadores prioritarios con restricciones sobre cuándo hacer pruebas cero. No trivial
Por cierto, su última pregunta de ejemplo fue discutida en este foro por el usuario Sam Jones. Otra referencia de Ibarra.
fuente