{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:18:10Z","timestamp":1725549490788},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_5","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"49-57","source":"Crossref","is-referenced-by-count":0,"title":["Regular Languages, Unambiguous Concatenation and Computational Complexity"],"prefix":"10.1007","author":[{"given":"Denis","family":"Th\u00e9rien","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M., Th\u00e9rien, D.: Algebraic results on quantum automata. In: STACS, pp. 93\u2013104 (2004)","DOI":"10.1007\/978-3-540-24749-4_9"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1. In: STOC, pp. 1\u20135 (1986)","DOI":"10.1145\/12130.12131"},{"issue":"4","key":"5_CR3","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. Barrington","year":"1988","unstructured":"Barrington, D., Th\u00e9rien, D.: Finite monoids and the fine structure of NC 1. J. ACM\u00a035(4), 941\u2013952 (1988)","journal-title":"J. ACM"},{"issue":"2","key":"5_CR4","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1137\/0219016","volume":"19","author":"G. Bilardi","year":"1990","unstructured":"Bilardi, G., Preparata, F.: Characterization of associative operations with prefix circuits of constant depth and linear size. SIAM J.Computing\u00a019(2), 246\u2013255 (1990)","journal-title":"SIAM J.Computing"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. Bshouty","year":"1996","unstructured":"Bshouty, N., Cleve, R., Gavald\u00e0, R., Kannan, S., Tamon, C.: Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences\u00a052, 421\u2013433 (1996)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR6","unstructured":"Buhrman, H.: Private communication (2004)"},{"key":"5_CR7","first-page":"222","volume":"30","author":"A.K. Chandra","year":"1985","unstructured":"Chandra, A.K., Fortune, S., Lipton, R.: Unbounded fan-in circuits and associative functions. JCSS\u00a030, 222\u2013234 (1985)","journal-title":"JCSS"},{"key":"5_CR8","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/180139.181116","volume-title":"COLT","author":"Z. Chen","year":"1994","unstructured":"Chen, Z., Homer, S.: On learning counting functions with queries. In: COLT, pp. 218\u2013227. ACM Press, New York (1994)"},{"key":"5_CR9","volume-title":"Automata, Languages and Machines","author":"S. Eilenberg","year":"1976","unstructured":"Eilenberg, S.: Automata, Languages and Machines, vol.\u00a0B. Academic Press, New York (1976)"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Gavald\u00e0, R., Th\u00e9rien, D.: Learning expressions over monoids. In: STACS, pp. 283\u2013293 (2001)","DOI":"10.1007\/3-540-44693-1_25"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Gavald\u00e0, R., Th\u00e9rien, D.: Algebraic characterizations of small classes of boolean functions. In: STACS, pp. 331\u2013342 (2003)","DOI":"10.1007\/3-540-36494-3_30"},{"key":"5_CR12","unstructured":"Kouck\u00fd, M., Pudl\u00e1k, P., Th\u00e9rien, D.: Star-free languages needing linear number of wires (In preparation)"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Moore, C., Tesson, P., Th\u00e9rien, D.: Satisfiability of systems of equations over finite monoids. In: MFCS, pp. 537\u2013547 (2001)","DOI":"10.1007\/3-540-44683-4_47"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/3-540-60084-1_87","volume-title":"Automata, Languages and Programming","author":"J. Pin","year":"1995","unstructured":"Pin, J., Weil, P.: Polynomial closure and unambiguous product. In: F\u00fcl\u00f6p, Z., Gecseg, F. (eds.) ICALP 1995. LNCS, vol.\u00a0944, pp. 348\u2013359. Springer, Heidelberg (1995)"},{"key":"5_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of Formal Languages","author":"J.E. Pin","year":"1986","unstructured":"Pin, J.E.: Varieties of Formal Languages. Plenum, London (1986)"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev.\u00a03, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M. Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.: On finite monoids having only trivial subgroups. Inform. and Control\u00a08, 190\u2013194 (1965)","journal-title":"Inform. and Control"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF02194921","volume":"13","author":"M. Sch\u00fctzenberger","year":"1976","unstructured":"Sch\u00fctzenberger, M.: Sur le produit de concatenation non ambigu. Semigroup Forum\u00a013, 47\u201375 (1976)","journal-title":"Semigroup Forum"},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"Schwentick, T., Th\u00e9rien, D., Vollmer, H.: Partially-ordered two-way automata: A new characterization of DA. Developments in Language Theory, 239\u2013250 (2001)","DOI":"10.1007\/3-540-46011-X_20"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Simon, H.U.: Learning decision lists and trees with equivalence-queries. In: EuroCOLT, pp. 322\u2013336 (1995)","DOI":"10.1007\/3-540-59119-2_188"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Sipser, M.: Borel sets and circuit complexity. In: STOC, pp. 61\u201369 (1983)","DOI":"10.1145\/800061.808733"},{"key":"5_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic and Circuit Complexity","author":"H. Straubing","year":"1994","unstructured":"Straubing, H.: Finite Automata, Formal Logic and Circuit Complexity. Birkh\u00e4user, Basel (1994)"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Tesson, P., Th\u00e9rien, D.: Diamonds are forever: the variety DA. In: Gomez, G., Silva, P., Pin, J.E. (eds.) Semigroups, Algorithms, Automata and Languages, WSP (2002)","DOI":"10.1142\/9789812776884_0021"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Tesson, P., Th\u00e9rien, D.: Complete classifications of the communication complexity of regular languages. In: STACS, pp. 62\u201373 (2003)","DOI":"10.1007\/3-540-36494-3_7"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Th\u00e9rien, D., Wilke, T.: Over words, two variables are as powerful as one quantifier alternation. In: STOC, pp. 234\u2013240 (1998)","DOI":"10.1145\/276698.276749"},{"issue":"1","key":"5_CR26","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00224-003-1109-3","volume":"37","author":"D. Th\u00e9rien","year":"2004","unstructured":"Th\u00e9rien, D., Wilke, T.: Nesting until and since in linear temporal logic. Theory of Computing Systems\u00a037(1), 111\u2013131 (2004)","journal-title":"Theory of Computing Systems"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:58:58Z","timestamp":1605761938000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}