{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T22:58:35Z","timestamp":1752361115645},"reference-count":27,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p> We introduce a logic to express structural properties of automata with string inputs and, possibly, outputs in some monoid. In this logic, the set of predicates talking about the output values is parametric. We then consider three particular automata models (finite automata, transducers and automata weighted by integers here called sum-automata) and instantiate the generic logic for each of them. We give tight complexity results for the three logics with respect to the model-checking problem, depending on whether the formula is fixed or not. We study the expressiveness of our logics by expressing classical structural patterns characterising for instance finite ambiguity and polynomial ambiguity in the case of finite automata, determinisability and finite-valuedness in the case of transducers and sum-automata. As a consequence of our complexity results, we directly obtain that these classical properties can be decided in polynomial time. <\/jats:p>","DOI":"10.1142\/s0129054120410038","type":"journal-article","created":{"date-parts":[[2020,10,5]],"date-time":"2020-10-05T08:11:59Z","timestamp":1601885519000},"page":"711-748","source":"Crossref","is-referenced-by-count":1,"title":["A Pattern Logic for Automata with Outputs"],"prefix":"10.1142","volume":"31","author":[{"given":"Emmanuel","family":"Filiot","sequence":"first","affiliation":[{"name":"Formal Methods and Verification, Computer Science Department CP-212, Universit\u00e9 libre de Bruxelles, 1050 Brussels, Belgium"}]},{"given":"Nicolas","family":"Mazzocchi","sequence":"additional","affiliation":[{"name":"Formal Methods and Verification, Computer Science Department CP-212, Universit\u00e9 libre de Bruxelles, 1050 Brussels, Belgium"}]},{"given":"Jean-Fran\u00e7ois","family":"Raskin","sequence":"additional","affiliation":[{"name":"Formal Methods and Verification, Computer Science Department CP-212, Universit\u00e9 libre de Bruxelles, 1050 Brussels, Belgium"}]}],"member":"219","published-online":{"date-parts":[[2020,10,5]]},"reference":[{"issue":"2","key":"S0129054120410038BIB001","first-page":"117","volume":"8","author":"Allauzen C.","year":"2003","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"S0129054120410038BIB002","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008477"},{"key":"S0129054120410038BIB003","first-page":"104","volume-title":"Language and Automata Theory and Applications \u2014 7th International Conference, LATA 2013, Proceedings","author":"Bala S.","year":"2013"},{"issue":"1","key":"S0129054120410038BIB004","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0304-3975(01)00271-7","volume":"289","author":"B\u00e9al M.","year":"2002","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"S0129054120410038BIB005","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0304-3975(01)00214-6","volume":"292","author":"B\u00e9al M.","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"S0129054120410038BIB006","series-title":"Teubner Studienb\u00fccher: Informatik","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and Context-Free Languages","volume":"38","author":"Berstel J.","year":"1979"},{"issue":"3","key":"S0129054120410038BIB007","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(77)90049-4","volume":"5","author":"Choffrut C.","year":"1977","journal-title":"Theor. Comput. Sci."},{"key":"S0129054120410038BIB008","first-page":"213","volume-title":"STACS 86, 3rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings","author":"Choffrut C.","year":"1986"},{"issue":"1","key":"S0129054120410038BIB009","first-page":"91","volume":"7","author":"Cooper D. C.","year":"1972","journal-title":"Machine Intelligence"},{"key":"S0129054120410038BIB011","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1109\/LICS.2015.39","volume-title":"30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015","author":"Figueira D.","year":"2015"},{"key":"S0129054120410038BIB012","first-page":"133","volume-title":"34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014","author":"Filiot E.","year":"2014"},{"issue":"3","key":"S0129054120410038BIB013","doi-asserted-by":"crossref","DOI":"10.2168\/LMCS-11(3:14)2015","volume":"11","author":"Filiot E.","year":"2015","journal-title":"Logical Methods in Computer Science"},{"key":"S0129054120410038BIB014","first-page":"304","volume-title":"Developments in Language Theory \u2014 22nd International Conference, DLT 2018, Proceedings","author":"Filiot E.","year":"2018"},{"issue":"3","key":"S0129054120410038BIB015","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"Griffiths T. V.","year":"1968","journal-title":"J. ACM"},{"issue":"1","key":"S0129054120410038BIB016","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01744569","volume":"16","author":"Gurari E. M.","year":"1983","journal-title":"Mathematical Systems Theory"},{"key":"S0129054120410038BIB017","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054118400075"},{"key":"S0129054120410038BIB018","first-page":"681","volume-title":"Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Proceedings","author":"Klaedtke F.","year":"2003"},{"key":"S0129054120410038BIB019","first-page":"254","volume-title":"18th Annual Symposium on Foundations of Computer Science","author":"Kozen D.","year":"1977"},{"key":"S0129054120410038BIB021","first-page":"21","volume-title":"Proceedings of the London Mathematical Society","author":"Rosser B.","year":"1939"},{"key":"S0129054120410038BIB022","first-page":"588","volume-title":"Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Proceedings","author":"Sakarovitch J.","year":"2008"},{"issue":"3","key":"S0129054120410038BIB023","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1007\/s00224-009-9206-6","volume":"47","author":"Sakarovitch J.","year":"2010","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"S0129054120410038BIB024","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0002-9947-1984-0742421-9","volume":"284","author":"Scarpellini B.","year":"1984","journal-title":"American Mathematical Society"},{"issue":"3","key":"S0129054120410038BIB025","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1137\/0214044","volume":"14","author":"Stearns R. E.","year":"1985","journal-title":"SIAM J. Comput."},{"issue":"8","key":"S0129054120410038BIB026","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1007\/BF00264285","volume":"27","author":"Weber A.","year":"1990","journal-title":"Acta Inf."},{"issue":"1","key":"S0129054120410038BIB027","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1137\/0222014","volume":"22","author":"Weber A.","year":"1993","journal-title":"SIAM J. Comput."},{"issue":"2","key":"S0129054120410038BIB028","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1006\/inco.1995.1071","volume":"118","author":"Weber A.","year":"1995","journal-title":"Inf. Comput."},{"issue":"2","key":"S0129054120410038BIB029","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(91)90381-B","volume":"88","author":"Weber A.","year":"1991","journal-title":"Theor. Comput. Sci."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120410038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T08:59:53Z","timestamp":1605257993000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120410038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":27,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1142\/S0129054120410038"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120410038","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}