Index Problems for Game Automata

For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the nondeterministic, alternating, and weak Rab...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on computational logic 2016-11, Vol.17 (4), p.1-38
Main Authors: Facchini, Alessandro, Murlak, Filip, Skrzypczak, Michał
Format: Article
Language:English
Subjects:
Closures
Computation
Games
Hierarchies
Logic
Parity
Priorities
Trees
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c253t-9f9c1090ead7226371337eea22d87cff873c92d9b7fa7d8e05d1727f6f14f4aa3
container_end_page 38
container_issue 4
container_start_page 1
container_title ACM transactions on computational logic
container_volume 17
creator Facchini, Alessandro
Murlak, Filip
Skrzypczak, Michał
description For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the nondeterministic, alternating, and weak Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognizable by deterministic automata (the alternating variant trivializes). We investigate a wider class of regular languages, recognizable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognize languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy; that is, the alternating index problem does not trivialize anymore. Our main contribution is that all three index problems are decidable for languages recognizable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognized by a game automaton.
doi_str_mv 10.1145/2946800
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1880023721</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1880023721</sourcerecordid><originalsourceid>FETCH-LOGICAL-c253t-9f9c1090ead7226371337eea22d87cff873c92d9b7fa7d8e05d1727f6f14f4aa3</originalsourceid><addsrcrecordid>eNotkE1LAzEURYMoWKv4F2anm9G8l8m8ZFmKtoWCLhTchTQfUJlpajID-u9taVf3Lg4X7mHsHvgTQCOfUTet4vyCTUBKqnUjvy6PHXUtSMlrdlPKN-eAJHDCqtXOh9_qPadNF_pSxZSrhe1DNRuH1NvB3rKraLsS7s45ZZ-vLx_zZb1-W6zms3XtUIqh1lE74JoH6wmxFQRCUAgW0StyMSoSTqPXG4qWvApceiCk2EZoYmOtmLLH0-4-p58xlMH02-JC19ldSGMxoA6nUBDCAX04oS6nUnKIZp-3vc1_Brg5OjBnB-IfWuRLsQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1880023721</pqid></control><display><type>article</type><title>Index Problems for Game Automata</title><source>Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list)</source><creator>Facchini, Alessandro ; Murlak, Filip ; Skrzypczak, Michał</creator><creatorcontrib>Facchini, Alessandro ; Murlak, Filip ; Skrzypczak, Michał</creatorcontrib><description>For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the nondeterministic, alternating, and weak Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognizable by deterministic automata (the alternating variant trivializes). We investigate a wider class of regular languages, recognizable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognize languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy; that is, the alternating index problem does not trivialize anymore. Our main contribution is that all three index problems are decidable for languages recognizable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognized by a game automaton.</description><identifier>ISSN: 1529-3785</identifier><identifier>EISSN: 1557-945X</identifier><identifier>DOI: 10.1145/2946800</identifier><language>eng</language><subject>Closures ; Computation ; Games ; Hierarchies ; Logic ; Parity ; Priorities ; Trees</subject><ispartof>ACM transactions on computational logic, 2016-11, Vol.17 (4), p.1-38</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c253t-9f9c1090ead7226371337eea22d87cff873c92d9b7fa7d8e05d1727f6f14f4aa3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27923,27924</link.rule.ids></links><search><creatorcontrib>Facchini, Alessandro</creatorcontrib><creatorcontrib>Murlak, Filip</creatorcontrib><creatorcontrib>Skrzypczak, Michał</creatorcontrib><title>Index Problems for Game Automata</title><title>ACM transactions on computational logic</title><description>For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the nondeterministic, alternating, and weak Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognizable by deterministic automata (the alternating variant trivializes). We investigate a wider class of regular languages, recognizable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognize languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy; that is, the alternating index problem does not trivialize anymore. Our main contribution is that all three index problems are decidable for languages recognizable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognized by a game automaton.</description><subject>Closures</subject><subject>Computation</subject><subject>Games</subject><subject>Hierarchies</subject><subject>Logic</subject><subject>Parity</subject><subject>Priorities</subject><subject>Trees</subject><issn>1529-3785</issn><issn>1557-945X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2016</creationdate><recordtype>article</recordtype><recordid>eNotkE1LAzEURYMoWKv4F2anm9G8l8m8ZFmKtoWCLhTchTQfUJlpajID-u9taVf3Lg4X7mHsHvgTQCOfUTet4vyCTUBKqnUjvy6PHXUtSMlrdlPKN-eAJHDCqtXOh9_qPadNF_pSxZSrhe1DNRuH1NvB3rKraLsS7s45ZZ-vLx_zZb1-W6zms3XtUIqh1lE74JoH6wmxFQRCUAgW0StyMSoSTqPXG4qWvApceiCk2EZoYmOtmLLH0-4-p58xlMH02-JC19ldSGMxoA6nUBDCAX04oS6nUnKIZp-3vc1_Brg5OjBnB-IfWuRLsQ</recordid><startdate>20161101</startdate><enddate>20161101</enddate><creator>Facchini, Alessandro</creator><creator>Murlak, Filip</creator><creator>Skrzypczak, Michał</creator><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20161101</creationdate><title>Index Problems for Game Automata</title><author>Facchini, Alessandro ; Murlak, Filip ; Skrzypczak, Michał</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c253t-9f9c1090ead7226371337eea22d87cff873c92d9b7fa7d8e05d1727f6f14f4aa3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Closures</topic><topic>Computation</topic><topic>Games</topic><topic>Hierarchies</topic><topic>Logic</topic><topic>Parity</topic><topic>Priorities</topic><topic>Trees</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Facchini, Alessandro</creatorcontrib><creatorcontrib>Murlak, Filip</creatorcontrib><creatorcontrib>Skrzypczak, Michał</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>ACM transactions on computational logic</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Facchini, Alessandro</au><au>Murlak, Filip</au><au>Skrzypczak, Michał</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Index Problems for Game Automata</atitle><jtitle>ACM transactions on computational logic</jtitle><date>2016-11-01</date><risdate>2016</risdate><volume>17</volume><issue>4</issue><spage>1</spage><epage>38</epage><pages>1-38</pages><issn>1529-3785</issn><eissn>1557-945X</eissn><abstract>For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the nondeterministic, alternating, and weak Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognizable by deterministic automata (the alternating variant trivializes). We investigate a wider class of regular languages, recognizable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognize languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy; that is, the alternating index problem does not trivialize anymore. Our main contribution is that all three index problems are decidable for languages recognizable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognized by a game automaton.</abstract><doi>10.1145/2946800</doi><tpages>38</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1529-3785
ispartof ACM transactions on computational logic, 2016-11, Vol.17 (4), p.1-38
issn 1529-3785
1557-945X
language eng
recordid cdi_proquest_miscellaneous_1880023721
source Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list)
subjects Closures
Computation
Games
Hierarchies
Logic
Parity
Priorities
Trees
title Index Problems for Game Automata
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-11T18%3A32%3A49IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Index%20Problems%20for%20Game%20Automata&rft.jtitle=ACM%20transactions%20on%20computational%20logic&rft.au=Facchini,%20Alessandro&rft.date=2016-11-01&rft.volume=17&rft.issue=4&rft.spage=1&rft.epage=38&rft.pages=1-38&rft.issn=1529-3785&rft.eissn=1557-945X&rft_id=info:doi/10.1145/2946800&rft_dat=%3Cproquest_cross%3E1880023721%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c253t-9f9c1090ead7226371337eea22d87cff873c92d9b7fa7d8e05d1727f6f14f4aa3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1880023721&rft_id=info:pmid/&rfr_iscdi=true